Majority Element

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.

Brute Force

A straightforward approach is to count how many times each number appears.

1. Use a hash map to store the frequency of every number.
2. While counting, check whether any frequency becomes greater than n / 2.
3. Return that number.

This runs in linear time, but it needs extra memory for the hash map.

Time: O(n)

Space: O(n)

Another option is to sort the array and return the middle element, since the majority element must occupy the middle position. That uses less memory but takes O(n log n) time.

We can do better by finding the majority element in one pass with constant extra space.

Optimal Approach: Boyer-Moore Voting Algorithm

Keep two variables:

• candidate: the element we currently think is the majority.
• count: how much "support" the current candidate has.

Scan the array from left to right.

If count is 0, pick the current element as the new candidate.

If the current element equals candidate, increase count.

Otherwise, decrease count.

At the end, candidate is the majority element.

Code

class Solution {
    public:
    int majorityElement(vector<int>& nums) {
        int candidate = 0;
        int count = 0;

        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }

            if (num == candidate) {
                count++;
            } else {
                count--;
            }
        }

        return candidate;
    }
};

Why Does This Work?

Imagine a basket with 11 bananas and 5 apples. Bananas are the majority because they make up more than half of the 16 fruits.

Now follow one rule: one apple can cancel one banana.

1Bananas: 🍌🍌🍌🍌🍌🍌🍌🍌🍌🍌🍌
2Apples:  🍎🍎🍎🍎🍎
3 
4Cancel 5 pairs:
5🍌🍎  🍌🍎  🍌🍎  🍌🍎  🍌🍎
6 
7Left over: 🍌🍌🍌🍌🍌🍌

Even if every apple is used to cancel a banana, the apples run out first. There are always bananas left over.

This is exactly what the algorithm does. Every time count decreases, one copy of the candidate is cancelled by a different number.

The majority element is the banana. It appears more than n / 2 times, so all the other numbers combined are always fewer. They can never cancel every copy of it, which means the majority element is the one left standing as the final candidate.

Complexity

How to Explain It in an Interview