Majority Element II
Return all elements that appear more than ⌊n/3⌋ times. There can be at most two such elements.
Intuition
If three different values each appeared more than n/3 times, their counts would exceed n — impossible. So the answer holds at most two elements, and we can run Boyer-Moore voting with two candidates at once.
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
First, why the answer has at most two elements
This is the crucial counting argument. If three different values each appeared more than n/3 times, their combined count would exceed 3 × (n/3) = n — impossible in an array of length n. So at most two values can clear the n/3 bar. That bound is what makes a constant-space solution possible: we only ever need to track two candidates at once.
Run Boyer-Moore with two slots
Generalize the single-candidate vote to two. Keep candidates c1, c2 with counters k1, k2. A value matching either candidate bumps that counter. A value matching neither, when both counters are non-zero, decrements both — that's the three-way cancellation (one of each candidate against the newcomer) that mirrors the n/3 threshold, just as the n/2 problem cancelled two at a time. Empty slots adopt new candidates.
Voting narrows; a second pass verifies
Voting only guarantees that if answers exist they're among c1, c2 — it does not prove either actually qualifies. For example [1,2,3] leaves candidates that each appear only once. So make a second pass that counts the real frequency of each survivor and keeps only those strictly above n/3. This verification is order-independent, so it cleans up any transient mistakes the vote made mid-scan. O(n) time, O(1) space.
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.