The Boyer-Moore Majority Vote: Finding the Majority in One Pass

The core idea: pairing off opponents

Imagine every element in the array is a voter for a candidate value. The majority element is one that appears strictly more than ⌊n/2⌋ times. The physical intuition: if you pair up any two voters who disagree and have them annihilate each other, the majority — precisely because it holds more than half the ballots — cannot be fully cancelled. Whatever survives the mass annihilation must be the majority (if a majority exists at all).

Boyer-Moore turns this into a streaming device using just two variables:

• candidate — the value currently "holding the floor".
• count — a signed tally of how strongly it holds it.

The governing invariant is the crux: after processing any prefix, count equals the number of copies of candidate in that prefix minus the number of all other elements that would need to pair off against it. When count hits 0, every vote so far has been cancelled by an equal opposing vote, so the true majority of the remaining suffix is unchanged — you can safely restart with the next element as the new candidate.

The algorithm, step by step

The whole method is three rules applied to each element left to right:

• If count == 0, adopt the current element as the new candidate and set count = 1.
• Else if the element equals candidate, increment count (a supporting vote).
• Else, decrement count (an opposing vote pairs off with a supporter).

After one pass, candidate holds the only value that could be the majority. Here it is in compact pseudocode:

candidate = None
count = 0
for x in stream:
    if count == 0:
        candidate = x
        count = 1
    elif x == candidate:
        count += 1
    else:
        count -= 1
# candidate is the ONLY possible majority

Trace [2, 2, 1, 1, 1, 2, 2] (n = 7, majority needs ≥ 4): count goes 1, 2, 1, 0 (→ candidate 1), 1, 0 (→ candidate 2), 1. Final candidate = 2, which indeed appears 4 times. Notice the candidate flipped twice mid-stream yet landed correctly — the cancellations were exactly balanced until 2's surplus asserted itself.

The mandatory second pass — and why

Here is the single most-missed subtlety, and the one interviewers hunt for. Boyer-Moore always returns a candidate, even when no majority exists. Run it on [1, 2, 3]: count is 0→1(cand 1)→0(decrement, cand still 1)→1(cand 3)... you end holding some value with count ≥ 1, but none of them appears more than once in three slots. The algorithm's guarantee is conditional: if a majority exists, the survivor is it; it does not certify existence.

So the honest, production-correct routine is two passes:

# Pass 2: verify
if stream.count(candidate) > n // 2:
    return candidate
else:
    return None   # no majority

The verification pass is another Θ(n) with O(1) space, so the total is still linear and constant-space. Skipping it is a genuine correctness bug — a classic "passes the sample tests, fails on [1,2,3]" mistake. When the problem guarantees a majority exists (as LeetCode 169 does), you may drop pass two; otherwise never.

Correctness: why the survivor must be the majority

Let m be the true majority element with multiplicity k > n/2, so the other n − k < n/2 elements are non-majority. Consider each decrement or count-reset as pairing off one occurrence of the current candidate against one non-matching element — an annihilation of two distinct values. Every such pairing removes at most one copy of m (when m happened to be the candidate) together with one non-m element.

• There are only n − k non-majority elements available to be one half of a pairing.
• Each pairing consumes one non-majority element, so at most n − k pairings can ever complete.
• Those pairings destroy at most n − k copies of m. Since k > n − k, at least k − (n − k) = 2k − n ≥ 1 copies of m survive un-annihilated.

Whatever survives forces the final candidate to be m with count ≥ 1. This is essentially a weighted-majority / cancellation argument; formally you prove by induction that after each prefix, count · [candidate == m] + (contribution of the discarded pairs) preserves m's surplus. The surplus 2k − n is exactly the count you'd read when only two distinct values are present (every non-m element then pairs off); with three or more values the final count can be larger, so 2k − n is a lower bound on it — a tidy sanity check.

Complexity and why the constants are so small

Time: Θ(n) — exactly one comparison and one arithmetic op per element in the vote pass, plus one comparison per element in the verify pass. There is no hidden log factor, no rehashing amortization, no cache-hostile pointer chasing. It is a pure sequential scan, which is why it saturates memory bandwidth and vectorizes and prefetches beautifully.

Space: O(1) — two machine words (candidate, count) regardless of n or the number of distinct values k. Contrast the hash-map solution: Θ(n) average time but O(n²) worst-case (with adversarial hashing) and O(k) space, where k can be Θ(n). On a stream you cannot afford to store, or in an embedded/edge context with a few kilobytes of RAM, that O(1) is the entire reason the algorithm exists.

• Boyer-Moore: Θ(n) time, O(1) space, 2 passes, branch-predictable.
• Sort-and-pick-middle: Θ(n log n) — correct because the majority necessarily occupies index ⌊n/2⌋ after sorting, but strictly worse asymptotically and destroys input order.
• Divide & conquer: Θ(n log n) via the recurrence T(n) = 2T(n/2) + Θ(n), elegant but pointless here.

The Misra-Gries generalization: majority to heavy hitters

Boyer-Moore is the k = 2 case of a bigger idea. To find all elements appearing more than n/k times (there are fewer than k of them), Misra and Gries (1982) generalized the trick: keep a dictionary of up to k − 1 candidates with counts. On each element, increment its count if present; else if a free slot exists, add it with count 1; else decrement every counter and drop any that hit 0. This one-batch cancellation of k distinct values is exactly the Boyer-Moore pairing scaled up.

• For the classic majority (> n/2), set k = 2 → one candidate → pure Boyer-Moore.
• For "find elements > n/3" (LeetCode 229), k = 3 → keep up to two candidates.
• Space is O(k), time O(n log k) or O(n) with a hash map of the k−1 slots.

Misra-Gries is a cornerstone of streaming / sketch algorithms: it underlies frequent-item detection in databases, network flow monitoring (the "heavy hitters" that dominate traffic), and is a deterministic cousin of the probabilistic Count-Min Sketch. Like the original, it may over-report — the verify pass to confirm true frequencies is still required.

Where it runs, and the traps

In the wild: the two-candidate Misra-Gries variant is used for fault-tolerant replicated state (choosing a value a majority of replicas agree on), for consensus-adjacent "pick the dominant response" logic, in stream processors (Apache Flink / Spark approximate frequent-items), and in network telemetry where storing per-flow counters is infeasible. In hardware and embedded voting (triple-modular redundancy, sensor fusion) the O(1) footprint is decisive.

Pitfalls and edge cases:

• Forgetting the verify pass — returns garbage when no majority exists. The #1 bug.
• "Plurality" ≠ "majority" — the algorithm finds a strict > n/2 winner, not merely the most common element. [1,1,2,2,2,3,3] has plurality 2 but no majority; Boyer-Moore + verify correctly returns "none". Plurality needs full counting.
• Empty input — define behavior explicitly; candidate is undefined.
• Count overflow — on a stream of 2⁶³ identical elements, a 64-bit counter is fine, but be deliberate about the integer width.
• Equality semantics — for objects, x == candidate must be the intended equality (value vs. reference); a mismatched comparator silently breaks the invariant.
• It gives no frequency — count at the end is a net surplus (at least 2k − n, and larger when more than two distinct values appear), NOT the true k. Never report it as the occurrence count.

Finding the majority element: three approaches and their real bounds

Approach	Time	Extra space	Needs verify pass?
Boyer-Moore vote	Θ(n)	O(1)	Yes (to confirm > n/2)
Hash map counting	Θ(n) avg	O(k) distinct keys	No
Sort, take middle	Θ(n log n)	O(1)–O(n)	Yes (still verify)
Randomized sampling	O(n) expected	O(1)	Yes, per candidate
Divide & conquer	Θ(n log n)	O(log n) stack	Merges combine