LeetCode 169 – Majority Element

Majority Element has a hash-map answer everyone writes and a constant-space answer that looks like it cannot possibly be correct. Boyer–Moore voting is four lines, and the reason it works is a counting argument short enough to give out loud — which is exactly why the problem is asked.

The problem

Given an array of size n, return the element appearing more than ⌊n/2⌋ times. Such an element is guaranteed to exist. The follow-up asks for O(n) time and O(1) space.

[3,2,3]              -> 3
[2,2,1,1,1,2,2]      -> 2      appears 4 times out of 7
[1]                  -> 1
[6,6,6,7,7]          -> 6      3 of 5

More than half, strictly. Not "the most common" — the guarantee is much stronger than a plurality, and the algorithm depends on it entirely.

What the constraints rule out

The sorting answer is worth a sentence on its own: because the majority element occupies more than half the array, it must cover the middle index whichever way it sits. That is a genuinely neat observation and a perfectly good answer if O(n log n) is acceptable.

The voting algorithm

Hold a candidate and a count. Walk the array: a matching element is a vote for the candidate, a different one is a vote against. When the count hits zero, adopt the current element as the new candidate.

[2,2,1,1,1,2,2]

2  count 0 -> candidate 2, count 1
2  match      count 2
1  differ     count 1
1  differ     count 0
1  count 0 -> candidate 1, count 1
2  differ     count 0
2  count 0 -> candidate 2, count 1     -> answer 2

Why it works

Think of each "differ" step as cancelling a pair: one occurrence of the candidate against one occurrence of something else. Every time the count returns to zero, the prefix consumed so far has been perfectly paired off — as many majority elements cancelled as non-majority ones, at most.

The majority element appears more than n/2 times, so there are strictly fewer than n/2 other elements to cancel against. Pairing can therefore never exhaust it. Whatever survives at the end is the only thing that could have survived.

That argument is the answer. The code is a formality once it is stated, and reciting the code without it is the version that does not land.

Java

class Solution {
    public int majorityElement(int[] nums) {
        int candidate = nums[0];
        int count = 0;

        for (int num : nums) {
            // Count zero means everything so far has cancelled out; start fresh.
            if (count == 0) candidate = num;

            count += (num == candidate) ? 1 : -1;
        }

        return candidate;
    }
}

The count == 0 check comes before the vote, so adopting a new candidate immediately counts one vote for it. Doing it afterwards leaves the count at zero forever and the candidate never stabilises.

candidate is initialised from nums[0] only to satisfy the compiler; the first iteration overwrites it, since count starts at zero. Any value would do, and saying that is better than leaving a reader wondering whether the first element is special.

Python

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

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

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

        return candidate

None as the initial candidate makes the "it does not matter" explicit — the first element is guaranteed to replace it, because count is zero.

The guarantee is load-bearing

Without "a majority element always exists", this algorithm returns a candidate that may not be one. On [1,2,3] it returns 3, which appears once out of three.

The fix is a second pass counting the candidate's actual occurrences and returning it only if the count exceeds n/2 — still O(n) time and O(1) space. Raising this unprompted is the strongest thing you can say about the problem: the algorithm does not find the majority element, it eliminates every element that cannot be it, and those are different claims.

Complexity

Every element must be read — the majority element could be anywhere — so linear is optimal.

The generalisation

Majority Element II (229) asks for every element appearing more than ⌊n/3⌋ times. There can be at most two such elements, and the algorithm extends directly: keep two candidates and two counts, cancelling three at a time. The verification pass stops being optional there, because two candidates always survive whether or not they qualify.

The general form keeps k − 1 candidates to find everything appearing more than n/k times, which is the Misra–Gries algorithm and the basis of streaming frequent-item estimation. Mentioning that this is a streaming algorithm — one pass, constant memory, no random access — is what places it properly.

What the interviewer is checking

• That "more than half" is stronger than "most common", and that the algorithm needs it.
• The pairing argument, not just the loop.
• That the count == 0 adoption happens before the vote.
• That you volunteer the verification pass and say why it is normally unnecessary.
• The sorting solution and why nums[n/2] is correct.
• A single-element array.
• Bonus: the n/3 generalisation with two candidates.