Majority Element | Leetcode 169

Welcome to our deep dive on Majority Element (Leetcode 169). This problem is the classic introduction to the brilliant Boyer-Moore Voting Algorithm, allowing us to bypass HashMap counting entirely.

Problem Statement

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example: nums = [2,2,1,1,1,2,2] => Output: 2

Approach 1: HashMap Frequency Counting O(N) Space

The immediate brute-force instinct is to iterate through the array, storing the frequency of exactly every single number we encounter inside a HashMap or Dictionary.

1. Create a counts Map.
2. For each number in nums, increment its count.
3. If the count reaches (n / 2) + 1, we immediately return it!

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        counts = {}
        target = len(nums) // 2
        
        for num in nums:
            counts[num] = counts.get(num, 0) + 1
            if counts[num] > target:
                return num

Complexity Analysis

Approach 2: Boyer-Moore Voting Algorithm O(1) Space

Because the problem guarantees that the majority element appears more than n/2 times, it possesses a unique mathematical property: If we assign a +1 value to the majority element, and a -1 value to every other element combined, the total sum will always be categorically greater than 0.

We can simulate "canceling out" elements. Whenever we encounter two different elements, we pair them up and destroy both of them. Because the majority element strictly outnumbers all other elements combined, the only remaining survivor must inherently be the majority element.

1. Maintain a candidate tracker and a count variable.
2. When iterating, if count == 0, set the current element as the candidate.
3. If the current element matches the candidate, increment count.
4. If it does not match the candidate, decrement count.

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = 0
        candidate = None
        
        for num in nums:
            if count == 0:
                candidate = num
            count += (1 if num == candidate else -1)
            
        return candidate

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (169)