Boyer-Moore Voting

Boyer-Moore Majority Vote Algorithm

LeetCode 169 presents a deceptively simple problem that the majority vote algorithm solves: given an array of $n$ elements, find the element that appears more than $n/2$ times. A naive approach counts occurrences in a hash map, which works in $O(n)$ time but requires $O(n)$ space. Boyer-Moore achieves the same time complexity using only $O(1)$ space: no hash map, no sorting, just two variables.

The Cancellation Intuition

The key insight is that if you pair every occurrence of a non-majority element with one occurrence of the majority element and cancel both out, the majority element will always have survivors left over. More precisely: if an element appears more than $n/2$ times, it outnumbers all other elements combined. No matter how you pair it against opponents, it cannot be fully cancelled.

Boyer-Moore simulates this cancellation in a single pass. You maintain one candidate and a count. When count reaches zero, you've exhausted the "budget" of the current candidate: it has been cancelled out by as many opposites. You then declare the next element your new candidate with a fresh count of 1. When you see your current candidate again, you increment count; when you see anything else, you decrement it.

Walked Example: [2, 2, 1, 1, 1, 2, 2]

Let's trace through this array step by step.

Start:  candidate = None, count = 0

num=2:  count==0, so candidate=2, count=1
num=2:  matches candidate, count=2
num=1:  differs, count=1
num=1:  differs, count=0
num=1:  count==0, so candidate=1, count=1
num=2:  differs, count=0
num=2:  count==0, so candidate=2, count=1

Result: candidate = 2

The true majority element is 2 (appears 4 times out of 7). Notice how the first two 2s and first two 1s cancelled each other entirely. The remaining elements elected 2 as the final candidate.

The Code

def majority_element(nums):
    candidate = count = 0
    for num in nums:
        if count == 0:
            candidate = num
        count += 1 if num == candidate else -1
    return candidate

This is a remarkably compact implementation. The conditional expression on the last line handles both the increment and decrement in one statement. Because the problem guarantees a majority element exists, this single pass is sufficient.

When You Must Verify

The algorithm finds a candidate, not a confirmed majority. If the problem does not guarantee that a majority element exists, for example "return -1 if no majority element", you must verify the candidate with a second pass:

def majority_element_or_none(nums):
    candidate = count = 0
    for num in nums:
        if count == 0:
            candidate = num
        count += 1 if num == candidate else -1

    # Verification pass
    if nums.count(candidate) > len(nums) // 2:
        return candidate
    return -1

Without verification, the algorithm on an array like [1, 2, 3] would return 3 (the last element to become candidate), even though no element appears more than once.

Extension: n/3 Majority with Two Candidates

The follow-up LeetCode 229. Majority Element II asks for all elements appearing more than n/3 times. At most two such elements can exist (since three elements each exceeding n/3 would together exceed n). Boyer-Moore generalizes cleanly: maintain two candidate-count pairs and cancel triplets of three distinct values.

def majority_element_n3(nums):
    c1 = c2 = None
    k1 = k2 = 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

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

The order of the conditionals matters: you must check whether num matches an existing candidate before checking whether a slot is empty, otherwise you might assign the same number to two slots.

Complexity

The algorithm runs in $O(n)$ time: two passes at most, both linear. Space is $O(1)$: only a fixed number of candidate-count variables are used regardless of input size. This makes it ideal for streaming scenarios where you cannot store all elements in memory.

The general pattern extends to any threshold: finding elements appearing more than n/k times requires k-1 candidates. The complexity stays $O(n)$ time and $O(k)$ space, which is $O(1)$ for fixed k.

Recognizing this pattern

You're probably looking at Boyer-Moore voting when:

• You need to find a majority element (one that appears more than n/2 times) in O(n) time and O(1) space.
• The constraint explicitly forbids a hash map or sorting, or asks for constant extra memory.
• The problem generalizes to "all elements appearing more than n/3 times", where at most two such elements exist.
• You're processing a stream where you can't store the input but still need the dominant value.

Common templates:

• Single majority candidate: one counter, one candidate, flip on tie. Example: Majority Element.
• Two candidates for > n/3: track two candidates and counts, verify in a second pass. Example: Majority Element II.
• Verify step for unguaranteed majority: run the vote, then count occurrences of the survivor to confirm. Example: Check If a Number Is Majority Element in a Sorted Array.
• Streaming dominant value: extend voting to an online setting where you only see each element once. Example: Online Majority Element In Subarray.