The site's twelfth Greedy entry, and the first that asks a frequency
question instead of a scheduling or covering one: given a list of votes, is there a candidate who
received a strict majority — more than half — and if so, who? The obvious approach
tallies every candidate in a hash map and reads off whichever count clears half, which is correct
but spends O(n) extra space on the tally. Boyer–Moore's algorithm answers the
same question in one left-to-right pass using two variables total — a current candidate
and a counter — greedily backing whoever's ahead right now and discarding that guess the moment the
count runs out. The catch, and this page's main pitfall, is that the pass alone never proves a
majority exists; it only ever tells you who it would be, if one does.
Two presets, both processed vote by vote, left to right. Election (real majority)
is a 10-vote tally where A wins with 6 of 10 — watch the running candidate swing to
D, then B (twice), before A's own votes finally take over for
good. Split vote (no majority) is a 6-vote tally where nobody clears half — the
pass still ends holding some candidate, and the skip verification pass
checkbox shows what happens if you trust that candidate without checking it (see
Pitfalls).
Think of every vote for the current candidate as a person still standing, and every count-- as
that person stepping aside together with whoever just voted differently — a cancelling
pair, one for one. That's a real constraint on the bookkeeping: a cancelling pair is always two
unequal votes (the whole reason it triggers is that the new vote doesn't match the
candidate), so a true majority candidate can never be one half of a pair against another
copy of itself — every cancellation that removes one of its votes must spend one non-majority vote
to do it. On the default election preset, A holds 6 of the 10 votes and the other
three candidates (D, C, B×2) hold only 4 between them —
so at most 4 of A's 6 votes can ever be cancelled away before the non-A
votes needed to pair against them simply run out. At least 6 − 4 = 2 of
A's votes must survive every possible cancellation, uncancelled, all the way to the
end — and since whatever survives uncancelled is exactly what the running candidate/count ends up
holding, that guarantees A is still the final candidate, not just a plausible one.
The same argument works for any array with a true majority: if it has n votes and
one candidate holds m > n/2 of them, the other n − m < n/2 < m
votes can cancel at most n − m of the majority's own votes, leaving at least
m − (n − m) = 2m − n > 0 standing — so the vote can never fully erase a true
majority, on any input, for any reason. What it does not guarantee is who's holding the
lead at every point along the way: on the election preset, the running candidate is briefly
D (1 vote, immediately cancelled by C), then B twice (each
time immediately cancelled by the very next vote), before A ever takes the lead for
good at index 5. Only the final candidate is meaningful — nothing about an intermediate
leader is.
Two passes, both O(n), neither needing more than a couple of variables. The first is
the vote itself; the second is the check every real use of this algorithm needs and the naive
version above skips — see Pitfalls for exactly what goes wrong without
it:
function majorityVote(votes) {
let candidate = null;
let count = 0;
for (const v of votes) {
if (count === 0) {
candidate = v; // the old guess is gone; back a fresh one
count = 1;
} else if (v === candidate) {
count++;
} else {
count--; // cancel: this vote and one of candidate's are both spent
}
}
// verification pass — the tally above never proves a majority exists
let occurrences = 0;
for (const v of votes) if (v === candidate) occurrences++;
return occurrences > votes.length / 2 ? candidate : null;
}Skipping the verification pass reports a majority even when none exists — and the
candidate it names doesn't even have to be a plausible runner-up. The vote loop above
always ends holding some candidate, for any non-empty input; nothing about the loop itself
can produce "no answer." On the split-vote preset (A, A, B, B, C, A — A
leads with 3 of 6, short of the 4 a majority needs), the naive version confidently names
C, the single least-common vote in the entire array (1 occurrence, against
A's 3) — not a near-miss, a different candidate entirely, and the internal counter that
produced it has already decayed to 0 by the last vote. Checked across 20,000 random 4-to-16-vote
arrays engineered so no true majority exists in 16,900 of them: the naive/unverified version is
wrong 100% of the time in those 16,900 by construction (it always names some
candidate as "the majority" when none exists), and in 9,590 of the 16,900 (56.7%)
the candidate it names isn't even the single most-frequent vote in that array — the same failure
mode the split-vote preset shows, not a rare edge case.
The counter's final value is not the margin of victory. It's tempting to read
the leftover count as "how much" a candidate won by, the way a scoreboard would. On the election
preset, A actually wins by 6 − 4 = 2 votes — but the pass's own internal
counter ends at 4, double the true margin, because two of the three losing candidates
(D once, B twice) each briefly built up their own short-lived lead before
A's votes cancelled them back out, and every one of those side excursions spends a
non-A vote without ever touching the running count the way a smooth,
uninterrupted A-only cancellation would. Checked directly across the same 20,000
engineered-majority arrays used above (3,100 of which have a genuine majority): the leftover count
differs from the true margin in 1,938 of them (9.7%) — not a fluke of this one
hand-picked example.
Time: O(n) — two linear passes (vote, then verify), never a nested
loop or a sort. Space: O(1) beyond the input itself: one candidate
variable and one counter, full stop. That's a genuinely different trade-off from the obvious
hash-map tally, which is also O(n) time but spends O(n) space building a
full frequency table — this algorithm answers the identical question in the same time class while
giving that space back, because it never needs to remember more than one candidate's standing at
once.
This site's guide, Choosing a Greedy Strategy, compares this entry's cancellation-pair proof against the other eleven Greedy entries' own exchange, bound-matching, and no-wasted-proposal arguments.