Majority Element II
Majority Element II: return all elements that appear more than ⌊n/3⌋ times. There can be at most two such elements.
- 1 <= nums.length <= 5 * 10⁴
- -10⁹ <= nums[i] <= 10⁹
Intuition
Majority element ii finds all values appearing more than n/3 times. A counting argument bounds the answer before any algorithm is chosen:
- At most two such values can exist, since three values each exceeding n/3 would require more than n elements.
That bound is what makes the extended Boyer-Moore voting applicable — track exactly two candidates with two counters.
Each element is handled in a strict order of checks. If it matches either candidate, increment that counter. Otherwise, if either counter is zero, install the element there. Only if neither applies, decrement both counters.
The ordering is essential. Checking for a matching candidate must come before checking for an empty slot, or a repeated value can be installed in both slots at once, and the algorithm then tracks one value twice while missing the other.
Decrementing both counters is the generalisation of the original algorithm's cancellation: one occurrence of each candidate is paired off against the current element.
The part that cannot be skipped here is the second pass. Unlike the n/2 problem, no element is guaranteed to exceed n/3, so the two surviving candidates are merely the only possible answers. Their actual counts must be verified before either is returned:
On an input like [1, 2, 3], the algorithm produces candidates that appear only once each, and returning them without verification is wrong.
The result can hold zero, one, or two values, so the output is a list rather than a single number.
Boyer-Moore generalised: at most k-1 elements can appear more than n/k times, so tracking k-1 candidate slots suffices. For n/3 that means two candidates. The cancellation step is the heart — when a third distinct value arrives, it annihilates one vote from each candidate, and only a true majority survives that attrition.
Approach
Before reading on: prove to yourself that at most two elements can exceed n/3. Three of them would need more than n elements in total. That bound is what tells you how many candidate slots to keep.
Bound the answer first
At most two values can exceed n/3 — three would require more than n elements. That bound is what makes two-candidate voting sufficient.
Track two candidates
Maintain two candidate values with independent counters. This is the direct generalisation of the single-candidate algorithm.
Check matches before empty slots
Test whether the element matches an existing candidate first. Checking empty slots first lets one value occupy both, tracking it twice and missing the other.
Decrement both when neither matches
An element matching neither candidate cancels one occurrence of each. This pairing is what preserves any value frequent enough to survive.
Verify with a second pass
The verification pass is mandatory here. Unlike the n/2 problem, no qualifying element is guaranteed — on [1, 2, 3] the candidates appear once each.
Return a list
Zero, one, or two values may qualify, so the output is a list. Only candidates whose verified count exceeds n/3 are included.
Cost of the algorithm
Two linear passes give O(n) time and O(1) space, holding two candidates and two counters regardless of input size.
Solution & live demo
Common pitfalls
Skipping the verification pass
return [c for c in (cand1, cand2) if c is not None]
if c is not None and nums.count(c) > len(nums) // 3:
result.append(c)The voting phase guarantees that any true n/3 element ends up as a candidate, but not that every candidate exceeds n/3. On [1, 2, 3] both slots fill with values appearing once each. Only a second counting pass separates the real answers.
Ordering the branches wrong
if count1 == 0:
cand1, count1 = x, 1
elif x == cand1:
count1 += 1if cand1 is not None and x == cand1:
count1 += 1
elif count2 is not None and x == cand2:
count2 += 1
elif count1 == 0:
...Matching an existing candidate must be tested before claiming an empty slot. Otherwise a value already held in slot 2 can be installed into a freshly emptied slot 1, so the same element occupies both slots and a genuine second majority is never tracked.
Decrementing only one counter on a mismatch
else:
count1 -= 1else:
count1 -= 1
count2 -= 1The invariant is that each non-matching element cancels one vote from every candidate — that's what makes the arithmetic work out for the n/3 threshold. Decrementing one side biases the survival of the other and can eliminate a true majority.
Edge cases
The mandatory verification pass discards both suspects, returning an empty list.
One slot fills, the other stays empty; verification keeps just the real majority.
Counters can swap candidates mid-scan, but the final verification is order-independent and corrects any transient mistake.