Boyer-Moore Majority Vote

Imagine a ballot box with a million votes. You want to know if any candidate got more than half of them — and you can only look at each ballot once, in any order, without saving them. How much scratch paper do you need?

The surprising answer, proved by Robert Boyer and J Strother Moore in 1981, is exactly two variables: a candidate and a count. Their algorithm streams through the sequence from left to right. Each new element either reinforces the current candidate (count goes up) or cancels one "copy" of it (count goes down). When the count hits zero, the candidate is swapped for the new element and the count resets to one. At the end, whatever candidate is left is the only possible majority winner — if a majority exists at all.

That final caveat matters: the algorithm is a filter, not a verifier. If fewer than half the elements are the same value, the surviving candidate is an artefact of the counting dynamics, not a true majority. A single verification pass over the array (or a second read of the stream) confirms or refutes the result.

The algorithm is provably optimal: any algorithm that identifies the majority element without a separate verification pass must read every element, and no algorithm can solve the problem with fewer than $O(n)$ time or with o(1) space while streaming. Boyer-Moore hits both bounds simultaneously.

Choose a preset sequence or build your own by clicking the colored buttons. Each click adds one vote to the stream. Press Step to process the next element and watch the candidate and count update — or hit Run all to let the algorithm finish in one go.

<div class="controls">
  <div class="presets">
    <span class="label">{{lbl_preset}}</span>
    <button id="preset1" type="button">{{btn_preset1}}</button>
    <button id="preset2" type="button">{{btn_preset2}}</button>
    <button id="preset3" type="button">{{btn_preset3}}</button>
  </div>
  <div class="adders">
    <span class="label">{{lbl_add_vote}}</span>
    <button id="addA" type="button" class="vote-btn vote-a">A</button>
    <button id="addB" type="button" class="vote-btn vote-b">B</button>
    <button id="addC" type="button" class="vote-btn vote-c">C</button>
  </div>
</div>
<div class="stream-wrap">
  <div id="stream" class="stream"></div>
</div>
<div class="state-box">
  <div class="state-item">
    <div class="state-label">{{lbl_candidate}}</div>
    <div id="candidate" class="state-val val-candidate">—</div>
  </div>
  <div class="state-item">
    <div class="state-label">{{lbl_count}}</div>
    <div id="count" class="state-val">0</div>
  </div>
  <div class="state-item">
    <div class="state-label">{{lbl_step}}</div>
    <div id="step" class="state-val">0 / 0</div>
  </div>
</div>
<div id="result" class="result"></div>
<div class="btns">
  <button id="stepBtn" type="button">{{btn_step}}</button>
  <button id="runBtn" type="button">{{btn_run}}</button>
  <button id="resetBtn" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.controls { display: flex; flex-wrap: wrap; gap: .5rem 1.2rem; align-items: center; margin-bottom: .6rem; }
.label { font-size: .8rem; color: #555; font-weight: 600; white-space: nowrap; }
.presets, .adders { display: flex; align-items: center; gap: .4rem; flex-wrap: wrap; }
button { font: 600 13px system-ui, sans-serif; padding: .35rem .8rem; border-radius: 7px; cursor: pointer;
         border: 1px solid #1d3557; background: #1d3557; color: #fff; }
button.ghost { background: #fff; color: #1d3557; }
.vote-btn { font-size: 1rem; padding: .3rem .75rem; font-weight: 700; border: 2px solid; }
.vote-a { background: #d0e8ff; border-color: #3a7cbf; color: #1a3a5c; }
.vote-b { background: #ffe0e0; border-color: #c0392b; color: #5c1a1a; }
.vote-c { background: #e0f8e0; border-color: #27ae60; color: #1a5c2a; }
.stream-wrap { min-height: 48px; background: #f4f6f8; border-radius: 8px; padding: 6px 8px; margin-bottom: .6rem; overflow-x: auto; }
.stream { display: flex; flex-wrap: wrap; gap: 4px; align-items: center; min-height: 36px; }
.token { width: 32px; height: 32px; border-radius: 6px; display: flex; align-items: center; justify-content: center;
         font: 700 14px system-ui; border: 2px solid; transition: opacity .15s; }
.token.done { opacity: .38; }
.token.current { outline: 3px solid #f4a800; outline-offset: 2px; }
.tok-A { background: #d0e8ff; border-color: #3a7cbf; color: #1a3a5c; }
.tok-B { background: #ffe0e0; border-color: #c0392b; color: #5c1a1a; }
.tok-C { background: #e0f8e0; border-color: #27ae60; color: #1a5c2a; }
.state-box { display: flex; gap: .8rem; margin-bottom: .6rem; flex-wrap: wrap; }
.state-item { background: #eef1f5; border-radius: 8px; padding: .4rem .8rem; text-align: center; min-width: 72px; }
.state-label { font-size: .72rem; color: #666; text-transform: uppercase; letter-spacing: .05em; }
.state-val { font: 700 1.5rem ui-monospace, monospace; margin-top: 2px; }
.val-candidate.tok-A { color: #3a7cbf; }
.val-candidate.tok-B { color: #c0392b; }
.val-candidate.tok-C { color: #27ae60; }
.result { min-height: 1.6em; font-weight: 600; font-size: .95rem; margin-bottom: .5rem; }
.result.found { color: #0a7d33; }
.result.none { color: #b5390a; }
.result.pending { color: #555; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }

// Code not found

Notice what happens when a long run of the losing value arrives: the count collapses vote by vote, the candidate swaps, and then the true majority starts rebuilding its lead. The algorithm never "knows" about previous elements — it only ever holds two numbers. That is the magic: two scalars encode everything needed to identify the survivor.

Status: solved — Boyer & Moore, 1981. The problem of finding the majority element (an element appearing more than ⌊n/2⌋ times) in a read-once stream is fully resolved.

• Time: $O(n)$ — one pass over the input. You cannot do better because you must at least read every element once to be sure.
• Space: $O(1)$ — just two scalar variables, regardless of how large the stream or the elements are. This is the stunning part: most problems that must "remember" structure need space proportional to the input size.
• Why it works — the pairing argument: imagine you pair every element with a distinct element of a different value and discard both pairs. If a majority exists, it has more than n/2 copies, so after all pairings it will have at least one copy left over. Boyer-Moore simulates this pairing implicitly: count tracks "unpaired copies of the candidate," and every time a non-candidate appears it cancels one copy. The final survivor is exactly the element that would survive this pairing.
• The verification step: the algorithm guarantees that if a majority exists it will be the surviving candidate. But it makes no guarantee when no majority exists. A second $O(n)$ pass — or any way to count the candidate's occurrences — is needed to confirm. Some applications (e.g., distributed voting where the existence of a majority is given by protocol) can skip verification.
• Lower bounds: any comparison-based streaming algorithm needs Ω(n) time (it must see all elements) and Ω(1) space (it must remember at least the current candidate). Boyer-Moore is therefore tight on both dimensions.

Compare this to sorting-based majority-finding ($O(n \log n)$ time, $O(n)$ space for a copy) or a hash-map count ($O(n)$ time but $O(k)$ space where k is the number of distinct values). Boyer-Moore beats both when space is at a premium.

Finding "what dominates this stream?" is a recurring question across computer science and engineering:

• Distributed consensus: in a fault-tolerant replicated system, a coordinator can ask each node for its current value and run Boyer-Moore on the replies. If any value holds a quorum (majority) it is found in one round-trip with constant extra memory — critical in latency-sensitive protocols.
• Database query optimization: database engines use Boyer-Moore internally to detect skew — when one value dominates a column — and pick the right join or index strategy.
• Network traffic analysis: a router monitoring millions of packets per second can use Boyer-Moore to find the elephant flow (source address or application that dominates bandwidth) without storing a per-flow table.
• Voting and election verification: the algorithm underpins several published protocols for electronic vote tallying, where the existence of a majority winner simplifies audit.
• Data deduplication and compression: when scanning a block of nearly-identical records, Boyer-Moore identifies the "dominant" record that most others should be delta-compressed against.
• Teaching streaming algorithms: Boyer-Moore is the canonical example used to introduce the "sketch" paradigm — approximate summaries of a data stream stored in tiny space. It sits alongside Bloom filters as a must-know building block.

Boyer-Moore's majority vote algorithm is one of the cleanest results in all of algorithm design: an elegant counting argument, two variables, one pass, and a proof that nothing can do better.

It belongs to a rare class of algorithms that are both simple enough to fit on a business card and provably optimal. The pairing intuition — majority elements cannot all be cancelled — is the kind of insight that, once seen, makes the algorithm feel inevitable.

Understanding Boyer-Moore opens the door to the broader world of streaming algorithms, where the challenge is to extract meaningful information from a data torrent using only a tiny notebook. From Bloom filters to frequency sketches, the same philosophy of "compress without losing what matters" runs through every modern data-engineering toolkit.