How to Learn Boyer–Moore Majority Vote: Pairwise Cancellation, Candidate Invariants, Verification and Streaming

Wait, What?

You can find a strict majority in one pass with constant extra memory, but only if you understand what the counter actually means.

The Boyer–Moore majority vote algorithm is a compact lesson in invariants, cancellation and streaming computation. Its implementation can fit on a few lines, yet those lines are easy to memorize incorrectly. The useful learning target is not the code. It is the proof idea: pair off unequal elements, preserve the only candidate that could still be a strict majority, then verify when existence is not guaranteed.

Quick Answer

Learn it through strict-majority definition → cancellation model → candidate/count state → loop invariant → first-pass survivor → second-pass verification → streaming limits → generalization. The first pass identifies the only possible majority. It does not prove that a majority exists.

1. Define the Problem Precisely

A strict majority element appears more than n/2 times in a sequence of length n. This is stronger than being the mode. In the sequence [1,2,2,3,3], the values 2 and 3 are tied for most frequent, but neither is a strict majority because neither appears more than half the time.

That threshold is what makes constant-memory cancellation possible. If one value occurs more often than all other values combined, pairing one copy of the majority with one non-majority value can never eliminate every copy of the majority.

2. The Pairwise-Cancellation Mental Model

Imagine repeatedly deleting pairs of unequal elements. If a strict majority M existed before a deletion, M remains the only value capable of being a strict majority among what survives. Deleting one M with one non-M reduces both sides by one; deleting two non-M values does not hurt M at all.

Boyer–Moore performs this cancellation implicitly. It never stores the pairs. It stores only a current candidate and a count representing unmatched copies of that candidate in the portion processed so far.

3. The Two Variables

• candidate: the value currently surviving cancellation.
• count: how many unmatched copies of that candidate remain after cancellations in the processed prefix.

When count is zero, there is no survivor from the previous prefix, so the next element can safely become the new candidate. A matching element increases count. A different element cancels one unmatched candidate copy and decreases count.

4. The Core Algorithm

def majority_candidate(values):
    candidate = None
    count = 0

    for x in values:
        if count == 0:
            candidate = x
            count = 1
        elif x == candidate:
            count += 1
        else:
            count -= 1

    return candidate

If the problem guarantees that a strict majority exists, the returned candidate is the answer. If the input may have no majority, a second pass is required.

5. Trace the Counter, Not Just the Code

For [A, B, A, A, C, A, A], start with no candidate. A becomes candidate with count 1. B cancels it to 0. The next A becomes the new candidate. The following A raises count to 2, C lowers it to 1, and the final two As raise it again. A survives.

Now trace [A, B, C]. The algorithm still returns a candidate, because the first pass must return some survivor when the sequence is non-empty. But no strict majority exists. This is the example that prevents one of the most common errors: treating “survivor” as “verified majority.”

6. The Invariant That Makes It Work

After processing any prefix, that prefix can be partitioned into two parts: pairs of unequal values that have effectively cancelled, plus count unmatched copies of candidate. The algorithm does not materialize the partition, but its state is equivalent to one.

If a strict majority exists in the entire sequence, removing unequal pairs cannot remove its majority status relative to the remaining unpaired elements. Therefore the final survivor must be that majority value.

7. Verification Is a Separate Job

def majority(values):
    candidate = majority_candidate(values)
    if candidate is None:
        return None

    occurrences = sum(x == candidate for x in values)
    return candidate if 2 * occurrences > len(values) else None

This second pass makes the contract explicit. It is not an embarrassment or a patch. The first pass solves a candidate-identification problem; the second pass solves an existence-verification problem.

8. Complexity and Why It Matters

The voting pass is O(n) time and O(1) extra space. Verification is another O(n) pass with O(1) extra space. This is especially useful when the sequence is large and a frequency dictionary would be expensive or impossible.

But streaming changes the verification story. If the data source cannot be replayed and majority existence is not guaranteed, you cannot simply perform a second pass unless you retain the stream or obtain an external verification mechanism.

9. What the Counter Does Not Mean

The final count is not the frequency of the candidate. It is a net cancellation balance. A candidate that appears 70 times in a list may finish with a much smaller count because many copies were paired against other values. Always compute the true frequency separately when verification is required.

10. Majority Is Not Mode

The algorithm does not find the most frequent element when no strict majority exists. If frequencies are 40%, 35% and 25%, there is a mode but no strict majority. Boyer–Moore may return a survivor that is not the mode. The mathematical guarantee is tied specifically to the more-than-half threshold.

11. Generalization: From One Survivor to Several Counters

The Misra–Gries family generalizes the same cancellation idea to find items whose frequency may exceed n/k using a bounded number of counters. That is a neighbouring streaming-algorithm job, not part of the core Boyer–Moore proof. The conceptual bridge is useful: majority vote is the simplest member of a larger family of frequency-summary ideas.

12. Professional Edge Cases

• Empty input: decide whether to return None, raise an error or use a sentinel.
• Non-replayable streams: verification may require storage or a second data source.
• Equality semantics: objects must have a meaningful equality relation.
• Distributed data: do not assume local majority candidates can simply be majority-voted again without preserving enough summary information.
• Weighted votes: ordinary Boyer–Moore assumes each input item contributes equally.

13. Testing Strategy

Build tests that deliberately separate “majority exists” from “majority does not exist.” Include even and odd lengths, majority appearing late, alternating values, all-identical values, empty input and adversarial prefixes where the candidate changes repeatedly. For small random arrays, compare against a dictionary-based reference implementation.

14. Common Failure States

• Forgetting the verification pass when majority existence is not guaranteed.
• Returning the final count as the candidate’s frequency.
• Using >= n/2 instead of the strict > n/2 definition.
• Resetting the candidate at the wrong time when count reaches zero.
• Confusing majority element with mode.
• Claiming one-pass verification on a non-replayable stream without additional information.

15. From Beginner to Professional

Beginner: pair off unequal coloured tokens by hand. Foundation: trace candidate and count on short arrays. Intermediate: state the prefix cancellation invariant and explain the second pass. Advanced: prove correctness and connect the method to n/k heavy-hitter summaries. Professional: reason about replayability, equality semantics, distributed summaries and whether the strict-majority contract actually matches the production problem.

Learning Hall Boundary

This article owns the strict-majority voting algorithm: pairwise cancellation, candidate/count invariant, verification and streaming interpretation. It does not replace the existing Learning Hall streaming-algorithm overview, Count-Min/HyperLogLog sketching material or generic searching and selection articles.

Evidence Boundary

Robert S. Boyer and J Strother Moore described MJRTY, a fast majority-vote algorithm, and the University of Texas at Austin hosts the original exposition. The central guarantee is linear-time candidate identification with constant extra storage, followed by verification when existence is not assumed. The learning design here uses hand tracing, worked examples, explicit invariants and error cases because current computing-education guidance treats code reading, testing and debugging as core outcomes rather than optional afterthoughts.

Professional rule: the algorithm’s cleverness is not that a counter magically finds the winner. The cleverness is that unequal pairs can be discarded without destroying a true strict majority.