One Candidate Left Standing: The Boyer-Moore Voting Algorithm

You have an array of a million integers. Your job: find the element that appears more than half the time, using no extra memory.

The natural answer is a HashMap. Count every element, scan for the one that exceeds n/2. O(n) time, O(n) space. It works. But there is a better algorithm that does this with constant space: one that was invented in 1980, rejected by every journal Boyer and Moore submitted it to, and finally published a decade later in a festschrift for a colleague. It's non-obvious, and the proof is genuinely satisfying once you follow it.

The Boyer-Moore majority vote algorithm finds the majority element, if one exists, in a single pass through the data with O(1) extra space. The mental model: every time two different elements meet, they cancel each other out. The majority, having more copies than all other elements combined, cannot be fully cancelled.

Nobody wanted to publish it. The algorithm did not care.

The Obvious First Attempts

Look at what everyone reaches for first.

HashMap counting is the obvious instinct: traverse the array, count each element, find the one with count > n/2.

from collections import Counter

def majority_element(nums):
    counts = Counter(nums)
    return max(counts, key=counts.get)

O(n) time, O(n) space. In the worst case, half the array is distinct non-majority elements. You store n/2 entries in the map.

Sorting is even simpler: sort the array and the middle element is always the majority, since it occupies more than half the positions. O(n log n) time, and you rearrange the input.

Boyer-Moore: O(n) time, O(1) space, one pass, input untouched.

How the Cancellation Works

The algorithm holds two variables: a candidate and a count. Walk the array with these rules:

• If count == 0: the current element becomes the new candidate, count resets to 1.
• If the current element matches candidate: increment count.
• If it doesn't match: decrement count.

That's the entire algorithm. Two integers. One pass. You can fit it in a tweet and still have room for a smug comment about HashMap.

Each minority element cancels one copy of 3. Three cancellations happen. One 3 is left.

Walk through [3, 2, 3, 1, 3, 1, 3]:

Candidate = 3. Correct: 3 appears 4 times out of 7, which is more than half.

Now a slightly trickier case: [2, 1, 1, 2, 2].

Candidate = 2. 2 appears 3 times out of 5. Correct.

Notice what happened: the candidate changed from 2 to 1 and back to 2. The algorithm doesn't commit to an answer early. It keeps updating the candidate whenever the count bottoms out. Every decrement is a cancellation: the current element and one copy of the candidate annihilate each other, neither survives.

The algorithm has no memory of prior candidates. It doesn't need any. When count hits zero, the slate is clean and whoever shows up next inherits the crown.

Why It's Correct: The Pairing Proof

The correctness argument is a structural invariant maintained by induction.

The invariant: After processing any prefix of length k, the k elements partition into two groups:

1. count unpaired copies of the current candidate
2. (k - count) / 2 cancelled pairs, each pair containing two different elements

Proof by induction:

• Base case: k=0, count=0. Trivially true.
• Inductive step: Process element x given the invariant holds for k elements:
  • count == 0: x becomes the new candidate with count=1. We now have 1 unpaired copy of x, and (k - 0) / 2 = k/2 cancelled pairs. The invariant holds for k+1.
  • x == candidate: count increments to count+1. One more unpaired copy. Invariant holds.
  • x != candidate and count > 0: count decrements. We form a new cancelled pair from x and one previously-unpaired copy of candidate. Invariant holds.

Now apply this to the full array of n elements. After processing everything, the array partitions into count unpaired copies of candidate and (n - count) / 2 cancelled pairs.

Why the majority must survive: Suppose M appears more than n/2 times. In each cancelled pair, M can contribute at most one element. So M's cancellation loss is at most (n - count) / 2. Its remaining unpaired copies are at least:

occurrences(M) - (n - count) / 2
> n/2 - (n - count) / 2
= count / 2
>= 0

Strictly greater than zero. M has at least one surviving copy, which means the final candidate must be M. No other element can end up with more unpaired copies than M.

The contrapositive is equally useful: if no element appears more than n/2 times, the algorithm can output any arbitrary element. The pairing proof says nothing about that case. This is exactly why phase 2 exists.

The majority started with 4 copies. Each cancellation cost it one. Three losses later, one is still standing.

The Verification Pass You Always Forget

Phase 1 guarantees: if a majority element exists, it will be the candidate. It says nothing about what the candidate is when no majority exists.

Consider [1, 2, 3]. Count goes: candidate=1, count=1; count=0; candidate=3, count=1. Output: 3. But 3 appears once out of three elements. No majority here, and the algorithm handed you a wrong answer without apologizing. Phase 1 found the last candidate standing. You asked it the wrong question.

Always add the verification pass when the problem does not guarantee a majority exists:

def majority_element(nums):
    candidate, count = None, 0
    for num in nums:
        if count == 0:
            candidate = num
        count += 1 if num == candidate else -1
    # Phase 2: verify
    if sum(1 for n in nums if n == candidate) > len(nums) // 2:
        return candidate
    return None

The second pass costs O(n) and zero extra space. Total is still O(n) time, O(1) space.

LeetCode 169 guarantees a majority exists, so you can skip verification there and your code is still correct. LeetCode 229 (find all elements appearing more than n/3 times) makes no such guarantee, so verification is mandatory. The most common bug in Boyer-Moore implementations is skipping phase 2 when the problem doesn't promise a majority.

There is a second trap, and it will get you in an interview after you've already cleared the first one: count after phase 1 is not the number of times candidate appeared in the array. It is the net margin: occurrences of candidate minus occurrences of all other elements in the unresolved portion. The actual frequency of the candidate can be much higher than count suggests. Do not use it as a frequency check and skip phase 2. That is how you get a wrong answer with confidence.

Complexity at a Glance

There is no amortized analysis here. Every element is visited exactly once in phase 1 and once in phase 2. The O(n) bound is exact worst case, not amortized. No operation takes more than O(1) per element. No surprise factors hiding in the constant.

The algorithm is a streaming algorithm in the strictest sense. You can process elements from stdin, a network socket, or a sensor feed one at a time, maintaining only candidate and count. You never need to store the sequence. O(1) working memory regardless of stream length. Point a firehose at it and it doesn't blink.

Like the sliding window algorithm, Boyer-Moore is part of the family of single-pass, O(1)-space array techniques. Both exploit structural properties of the problem to avoid storing the full input.

Extending to n/3: Two Candidates

There can be at most two elements appearing more than n/3 times in any array. The argument is direct: suppose three elements each appeared more than n/3 times. They'd collectively account for more than n elements. Impossible.

So you maintain two candidates and two counters. For each element:

1. If it matches candidate1, increment count1.
2. Else if it matches candidate2, increment count2.
3. Else if count1 == 0, assign this element as candidate1 with count1 = 1.
4. Else if count2 == 0, assign this element as candidate2 with count2 = 1.
5. Otherwise, decrement both count1 and count2.

The ordering of these checks is critical. You must test whether the element matches an existing candidate before checking for an empty slot. If you flip the order and check for empty slots first, you might assign the same element to both candidates, producing a duplicate. This is the kind of bug that passes most test cases and fails on the one interviewer-crafted input that has a repeated first element.

Step 7 is the triple cancel: element 3 matches neither candidate, so both counters take the hit.

def majority_elements_n3(nums: list[int]) -> list[int]:
    c1, c2, k1, k2 = None, None, 0, 0

    for num in nums:
        if num == c1:
            k1 += 1
        elif num == c2:
            k2 += 1
        elif k1 == 0:
            c1, k1 = num, 1
        elif k2 == 0:
            c2, k2 = num, 1
        else:
            k1 -= 1
            k2 -= 1

    # Verification is mandatory: the threshold is not guaranteed
    threshold = len(nums) // 3
    return [c for c in (c1, c2) if c is not None and nums.count(c) > threshold]

Step 5 (decrement both) is cancelling a triple: one copy of each candidate plus the current element. Any element appearing more than n/3 times has more copies than the remaining elements can triple-cancel away.

Misra-Gries generalizes this further. For elements appearing more than n/k times, maintain k-1 candidates with k-1 counters. When all k-1 counters are positive and the current element matches none, decrement every counter by 1. This cancels a k-tuple of distinct elements. Any element appearing more than n/k times survives. Space: O(k). Time: O(n). Boyer-Moore is Misra-Gries at k=2.

One Structure, Every Language

The implementations below show the full majority vote (n/2 threshold) with both phases.

def majority_element(nums: list[int]) -> int | None:
    candidate, count = None, 0
    for num in nums:
        if count == 0:
            candidate = num
        count += 1 if num == candidate else -1
    if sum(1 for n in nums if n == candidate) > len(nums) // 2:
        return candidate
    return None

Where the Boyer-Moore Voting Algorithm Actually Gets Used

Stream majority detection. The algorithm processes one element at a time with two variables of state. If you're reading from a firehose, you never buffer the stream. Log pipelines, network monitoring: anywhere you need frequency estimates in real time without accumulating data.

Space-constrained environments. Embedded systems and kernel code, where dynamic allocation is unavailable or expensive. Two integers is the total overhead. There are microcontrollers out there running Boyer-Moore right now and they have no idea it has a name.

Election and vote aggregation. Given a list of votes, find the winner in a single scan without a count table. Boyer and Moore's original motivation was fault-tolerant hardware: given a cluster of redundant computers all computing the same thing, you need a majority opinion to determine the correct output without a vote-counting table.

Data integrity checks. If a data stream should be dominated by one value (heartbeat signals, protocol headers, sensor readings in a stable state), Boyer-Moore detects the dominant value and a failed verification indicates instability.

Dominant category detection. Finding the majority pixel color in a region or the majority label in a dataset chunk: same pattern, different domain.

When Boyer-Moore Is the Right Call

Signals that Boyer-Moore is the right tool:

• The problem asks for an element appearing "more than n/2 times" or "more than n/k times"
• O(1) space is required or explicitly mentioned as a follow-up optimization
• The data arrives as a stream and you can't store it all
• The problem says "at most k elements can satisfy the condition" and k is small

Two worked examples.

Example 1: LeetCode 169, Majority Element

Problem: given an integer array where a majority element is guaranteed to exist, find it. Majority means appearing more than n/2 times.

Why Boyer-Moore: the guarantee eliminates the false-positive problem, so you can skip phase 2. The phrase "guaranteed to appear more than n/2 times" is the pairing invariant stated in plain English. The majority can't be cancelled because the opposing elements aren't numerous enough.

def majorityElement(nums: list[int]) -> int:
    candidate, count = 0, 0
    for num in nums:
        if count == 0:
            candidate = num
        count += 1 if num == candidate else -1
    return candidate  # Majority is guaranteed, no verification needed

Example 2: LeetCode 229, Majority Element II

Problem: given an integer array, return all elements appearing more than n/3 times.

Why Boyer-Moore: the upper bound on candidates (at most two) comes from the same argument as before. Three elements each appearing > n/3 times would collectively exceed the array length. So you need the two-candidate variant. No element is guaranteed to hit the threshold, so both candidates must be verified in phase 2.

def majorityElement(nums: list[int]) -> list[int]:
    c1, c2, k1, k2 = None, None, 0, 0

    for num in nums:
        if num == c1:
            k1 += 1
        elif num == c2:
            k2 += 1
        elif k1 == 0:
            c1, k1 = num, 1
        elif k2 == 0:
            c2, k2 = num, 1
        else:
            k1 -= 1
            k2 -= 1

    threshold = len(nums) // 3
    return [c for c in (c1, c2) if c is not None and nums.count(c) > threshold]

The general recognition signal. If a problem asks you to find elements that "dominate" a sequence by frequency, and the definition of dominate maps to a threshold like n/k, check whether the number of possible candidates is bounded. If it is, Boyer-Moore applies. HashMap solutions work but fail space constraints. Sorting works but costs O(n log n). Boyer-Moore is the only path to O(n) time and O(1) space simultaneously.

The Short Version

• Boyer-Moore majority vote: O(n) time, O(1) space, exact worst-case bounds with no amortized analysis.
• Phase 1 finds a candidate via pairwise cancellation. Phase 2 verifies it counts to find the real frequency.
• Skip phase 2 only when the problem guarantees a majority exists. Otherwise you'll produce wrong answers.
• The final count after phase 1 is the net margin, not the actual frequency of the candidate. Don't confuse them.
• Correctness rests on a pairing invariant: after all cancellations, the majority element has more survivors than any other element can claim.
• For n/3 threshold: two candidates, decrement both on a non-matching element, verify both afterward.
• Check existing candidates before assigning to empty slots in the n/3 variant, or you risk a duplicate candidate bug.
• For arbitrary n/k: Misra-Gries with k-1 candidates and O(k) space is the generalization.
• The algorithm is a true streaming algorithm: two variables of state, regardless of stream length.
• Most common bug: forgetting the verification pass when the problem doesn't promise a majority. Second most common: forgetting the bug above after you already knew about it.

If you want to practice problems like these on a voice-based mock interviewer that gives rubric feedback on your reasoning, SpaceComplexity is worth a try. Explaining why the verification pass matters is the kind of thing that separates a clean solution from a great interview answer.

Further Reading

• Boyer-Moore Majority Vote Algorithm (Wikipedia)
• Boyer-Moore Majority Voting Algorithm (GeeksforGeeks)
• Misra-Gries Heavy Hitters Algorithm (Wikipedia)
• LeetCode 169: Majority Element
• LeetCode 229: Majority Element II