Majority Element II (More Than n/3 Times)
WHAT IT SAYS
Find every element that appears more than floor(n/3) times in the array. There can be at most two of them.
WHAT IT'S REALLY ASKING
"Treat it as a war of attrition: whenever three pairwise-different values show up, one copy of each annihilates. A value holding more than a third of the array has too many soldiers to ever be wiped out — so how many survivors can there possibly be, and how much memory does it take to hold them?"
Count every element by rescanning
O(n^2) time, O(1) spaceFor each element, sweep the whole array counting how many times it appears; if the count clears n/3 and you have not already recorded it, add it to the answer.
WHERE THE WORK IS WASTED — You build a complete histogram to read off at most two numbers from it. Every value that loses still costs you a full O(n) pass, and a value appearing 500 times is counted 500 separate times — 500 identical sweeps producing 500 identical answers. The question was 'who is above the line', and you answered 'here is the exact height of everyone'.
Tally with a hash map
O(n) time, O(n) spaceOne pass to build value -> count, one pass over the map to collect anything above n/3. Fast, obvious, and correct.
WHERE THE WORK IS WASTED — Time is now optimal, so the only thing left to attack is the memory — and it is memory spent on the guaranteed losers. The map faithfully stores counts for elements appearing once, whose fate was sealed the moment you saw them. You are keeping a full census when the answer has at most two rows.
Delete three distinct values; the winners stay winners.
Here is the operation: pick any three pairwise-different values currently in the array and delete one copy of each. Claim: this cannot destroy a true answer. Suppose x appears more than n/3 times. The three values you deleted are all different, so at most one of them was x — x loses at most one copy, while the array's length drops by exactly three. Does x still clear the bar? Before, count(x) > n/3. After, you need count(x) - 1 > (n-3)/3, which is count(x) - 1 > n/3 - 1, which is count(x) > n/3 — precisely what you already knew. The property survives the deletion untouched. It is an invariant. So apply the operation over and over. Each application removes three elements, so it terminates, and it can only stop when fewer than three DISTINCT values remain. At most two values are left standing — and by the invariant, every genuine majority element must be among them. Two survivors, so two slots. That is where the two counters come from: not from cleverness, but from the arithmetic of what cancellation cannot kill. One thing the argument does NOT give you, and you must not pretend otherwise. It says 'if x is a majority then x survives'. It says nothing about the reverse. An array of three unique values leaves survivors with no majority at all. Cancellation produces suspects, never convictions — which is why a verification pass is not optional politeness, it is part of the algorithm.
Two slots, two counters, then verify
O(n) time, O(1) space, two passesWalk once holding two candidate values and two counts. If the element equals a candidate, increment that count. Otherwise, if a count is zero, evict that slot and install the element with count 1. Otherwise the element differs from both candidates — that is your three distinct values, so decrement both counts and let all three annihilate. Then take a second pass and actually count the two survivors, keeping only those that really clear n/3.
Mutual Annihilation
YOU'LL SEE IT AGAIN WHEN
- The threshold is a fraction of n (more than n/2, n/3, n/k), which by itself caps the number of possible answers at a tiny constant.
- You are asked for the elements above a frequency line, not for the frequencies themselves — so the full histogram is over-delivery.
- Cancelling groups of distinct elements would shrink n faster than it shrinks the leader's count, meaning the leader's advantage is robust to deletion.