LeetCode 169: Majority Element

Problem Restatement

We are given an integer array nums of size n.

We need to return the majority element.

The majority element is the value that appears more than:

n // 2

times.

The problem guarantees that a majority element always exists. LeetCode also asks whether we can solve it in linear time and constant extra space.

Input and Output

Example function shape:

def majorityElement(nums: list[int]) -> int:
    ...

Examples

Example 1:

nums = [3, 2, 3]

The value 3 appears twice.

The array length is 3, so the majority threshold is:

3 // 2 = 1

Since 2 > 1, the answer is:

3

Example 2:

nums = [2, 2, 1, 1, 1, 2, 2]

The value 2 appears 4 times.

The array length is 7, so the majority threshold is:

7 // 2 = 3

Since 4 > 3, the answer is:

2

First Thought: Count Frequencies

A simple solution is to count how many times each number appears.

class Solution:
    def majorityElement(self, nums: list[int]) -> int:
        count = {}

        for num in nums:
            count[num] = count.get(num, 0) + 1

            if count[num] > len(nums) // 2:
                return num

This is correct and runs in O(n) time.

But it uses O(n) extra space in the worst case.

The follow-up asks for constant extra space.

Key Insight

Use Boyer-Moore voting.

Think of different numbers canceling each other out.

If one value appears more than half the time, then even after pairing it with every different value, at least one copy of it remains.

So we keep:

When we see the same value as candidate, increase count.

When we see a different value, decrease count.

If count becomes 0, all previous votes have canceled out, so we choose the next value as a new candidate.

Because the true majority appears more than all other values combined, it survives this cancellation process.

Algorithm

Initialize:

candidate = None
count = 0

For each number num in nums:

1. If count == 0, set candidate = num.
2. If num == candidate, increment count.
3. Otherwise, decrement count.

At the end, return candidate.

The problem guarantees that a majority element exists, so no second verification pass is needed.

Walkthrough

Use:

nums = [2, 2, 1, 1, 1, 2, 2]

Return:

2

Even though the candidate temporarily changes to 1, the true majority 2 still survives by the end.

Correctness

The algorithm cancels pairs of different values.

Removing one majority element together with one non-majority element does not change the fact that the majority value is still the only value that can appear more than half of the remaining uncanceled elements.

Because the majority element appears more than all other elements combined, it cannot be fully canceled by different values.

Whenever count becomes zero, the processed prefix has been fully canceled into pairs of different values. That prefix cannot change the majority of the remaining suffix.

Therefore, after scanning the whole array, the remaining candidate must be the majority element.

Since the problem guarantees that a majority element exists, returning candidate is correct.

Complexity

Implementation

class Solution:
    def majorityElement(self, nums: list[int]) -> int:
        candidate = None
        count = 0

        for num in nums:
            if count == 0:
                candidate = num

            if num == candidate:
                count += 1
            else:
                count -= 1

        return candidate

Code Explanation

Start with no candidate:

candidate = None
count = 0

When the vote balance is zero, choose the current value:

if count == 0:
    candidate = num

Then update the vote balance:

if num == candidate:
    count += 1
else:
    count -= 1

A same value supports the candidate.

A different value cancels one vote.

At the end:

return candidate

returns the majority element.

Alternative: Sorting

If we sort the array, the majority element must appear at the middle index.

class Solution:
    def majorityElement(self, nums: list[int]) -> int:
        nums.sort()
        return nums[len(nums) // 2]

This works because a value that appears more than half the time must cover the median position.

Complexity:

The Boyer-Moore version is better for the follow-up.

Testing

def run_tests():
    sol = Solution()

    assert sol.majorityElement([3, 2, 3]) == 3
    assert sol.majorityElement([2, 2, 1, 1, 1, 2, 2]) == 2
    assert sol.majorityElement([1]) == 1
    assert sol.majorityElement([1, 1, 2]) == 1
    assert sol.majorityElement([-1, -1, -1, 2, 3]) == -1
    assert sol.majorityElement([6, 5, 5]) == 5

    print("all tests passed")

run_tests()