Find majority element

The problem, simply

You get an array of n numbers. The majority number is one that appears more than n / 2 times, so more than half of all boxes hold it.

Return it. If no number appears more than half the time, return -1.

A story to remember it

Picture it

Examples

Way 1: the simple way

For each box, count how many boxes hold the same number. If the count is more than n / 2, that number wins.

class Solution {
    public int majorityElement(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < n; j++) {
                if (arr[j] == arr[i]) count++;
            }
            if (count > n / 2) return arr[i];   // more than half
        }
        return -1;
    }
}

How long it takes: every box counts against every box, O(n^2). Extra room: O(1).

Way 2: the clever way

Play the cancelling game with one leader and one counter. The counter is the height of a pile of leader votes that nobody has cancelled yet.

1. Start with an empty pile (count = 0).
2. For each vote: if the pile is empty, this vote becomes the leader and the pile has 1.
3. Else if the vote matches the leader, the pile grows by 1.
4. Else the vote cancels one leader vote, and the pile shrinks by 1.
5. At the end, the leader is the only possible majority. Count it once more to check it really has more than half.

class Solution {
    public int majorityElement(int[] arr) {
        int leader = 0, count = 0;
        for (int x : arr) {
            if (count == 0) {            // pile is empty, new leader
                leader = x;
                count = 1;
            } else if (x == leader) {
                count++;                 // one more unpaired leader vote
            } else {
                count--;                 // x cancels one leader vote
            }
        }
        int real = 0;                    // check: the leader might not be a majority
        for (int x : arr) if (x == leader) real++;
        return real > arr.length / 2 ? leader : -1;
    }
}

How long it takes: two walks over the array, O(n). Extra room: two numbers, O(1).

Watch out for

• "More than half" means count > n / 2 with integer division. For n = 4, you need 3, not 2.
• The leader at the end is not the most common number in general. It is only guaranteed to be the majority when one exists.
• Making the cancelling vote the new leader. The vote that brings the pile down to 0 is used up by the cancel. The next vote becomes the leader.

What interviewers ask next

• Other ways? A hash map of counts, O(n) time and O(n) room. Or sort and take the middle box, O(n log n), since a majority must cover the middle.
• Find all numbers that appear more than n / 3 times (LeetCode 229). At most two can exist. Keep two leaders and two counters, cancel a vote against both when it matches neither, then verify both.
• More than n / k times? Keep k - 1 leaders with counters. That is the Misra-Gries idea, used for finding heavy hitters in data streams.
• Why does it work? Each cancel removes one majority vote at most and one non-majority vote at least. The majority has more votes than everyone else together, so it cannot be cancelled away.
• Can you do it on a stream you see only once? Yes, the first pass works on a stream. The check needs a second pass, or a promise that a majority exists.

Remember this

Grown-up words: the cancelling game is the Boyer-Moore majority vote algorithm, the leader is the candidate, the pile height is the count, and the second walk is the verification pass.