Introduction

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)O(n) time or with o(1) space while streaming. Boyer-Moore hits both bounds simultaneously.

Try It

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">Preset:</span>
    <button id="preset1" type="button">A wins (7/12)</button>
    <button id="preset2" type="button">No majority</button>
    <button id="preset3" type="button">Late surge</button>
  </div>
  <div class="adders">
    <span class="label">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">Candidate</div>
    <div id="candidate" class="state-val val-candidate">—</div>
  </div>
  <div class="state-item">
    <div class="state-label">Count</div>
    <div id="count" class="state-val">0</div>
  </div>
  <div class="state-item">
    <div class="state-label">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">Step ▶</button>
  <button id="runBtn" type="button">Run all ⏩</button>
  <button id="resetBtn" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Boyer-Moore Majority Vote algorithm
// Keep (candidate, count). For each element:
//   if count == 0 → set candidate = element, count = 1
//   else if element == candidate → count++
//   else → count--
// After one pass the surviving candidate is the only possible majority.
// A second verification pass checks whether it actually appears > n/2 times.

const PRESETS = {
  preset1: list('AAABBAABABAA'),      // A appears 7/12 times → majority
  preset2: list('AABBCCAABBCC'),      // no majority
  preset3: list('BBBBBBAAAAAAAAA'),   // B leads, then A surges to majority (9/15)
};

function list(s){ return s.split(''); }

let seq = [...PRESETS.preset1];
let pos = 0;
let candidate = null;
let count = 0;

function colorClass(v){ return v ? 'tok-' + v : ''; }

function render(){
  // stream
  const sc = document.getElementById('stream');
  sc.innerHTML = '';
  seq.forEach((v, i) => {
    const d = document.createElement('div');
    d.className = 'token ' + colorClass(v) + (i < pos ? ' done' : '') + (i === pos ? ' current' : '');
    d.textContent = v;
    sc.appendChild(d);
  });
  // state
  const cv = document.getElementById('candidate');
  cv.textContent = candidate || '—';
  cv.className = 'state-val val-candidate ' + colorClass(candidate);
  document.getElementById('count').textContent = count;
  document.getElementById('step').textContent = pos + ' / ' + seq.length;
  // result
  const r = document.getElementById('result');
  if(pos < seq.length){ r.textContent = ''; r.className = 'result pending'; }
  else { verify(r); }
}

function verify(r){
  if(!candidate){ r.textContent = 'Stream is empty.'; r.className='result none'; return; }
  const freq = seq.filter(v => v === candidate).length;
  if(freq * 2 > seq.length){
    r.textContent = fmt('✓ %candidate%  is the majority (%freq% / %length% votes).', { candidate: candidate, freq: freq, length: seq.length });
    r.className = 'result found';
  } else {
    r.textContent = fmt('✗ %candidate%  survived but is not a majority (%freq% / %length%). No majority exists.', { candidate: candidate, freq: freq, length: seq.length });
    r.className = 'result none';
  }
}

function step(){
  if(pos >= seq.length) return;
  const v = seq[pos];
  if(count === 0){ candidate = v; count = 1; }
  else if(v === candidate){ count++; }
  else { count--; }
  pos++;
  render();
}

function runAll(){
  if(pos >= seq.length) return;
  while(pos < seq.length) {
    const v = seq[pos];
    if(count === 0){ candidate = v; count = 1; }
    else if(v === candidate){ count++; }
    else { count--; }
    pos++;
  }
  render();
}

function reset(){
  pos = 0; candidate = null; count = 0;
  render();
}

function loadPreset(key){
  seq = [...PRESETS[key]];
  pos = 0; candidate = null; count = 0;
  render();
}

function addVote(v){
  seq.push(v);
  render();
}

document.getElementById('stepBtn').addEventListener('click', step);
document.getElementById('runBtn').addEventListener('click', runAll);
document.getElementById('resetBtn').addEventListener('click', reset);
document.getElementById('preset1').addEventListener('click', () => loadPreset('preset1'));
document.getElementById('preset2').addEventListener('click', () => loadPreset('preset2'));
document.getElementById('preset3').addEventListener('click', () => loadPreset('preset3'));
document.getElementById('addA').addEventListener('click', () => addVote('A'));
document.getElementById('addB').addEventListener('click', () => addVote('B'));
document.getElementById('addC').addEventListener('click', () => addVote('C'));

render();
Result
Console

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.

The Real Complexity

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)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)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)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(nlog⁡n)O(n \log n) time, O(n)O(n) space for a copy) or a hash-map count (O(n)O(n) time but O(k)O(k) space where k is the number of distinct values). Boyer-Moore beats both when space is at a premium.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/boyer-moore-majority/Content licensed under CC BY-NC 4.0.