Majority Element: Boyer-Moore Voting in O(1) Space

Majority element looks like a counting problem, and a hash map solves it in one line. The interesting version asks for O(1) extra space, and the answer, Boyer-Moore voting, is one of the shortest algorithms you will ever be asked to explain. It is also easy to explain badly. The code is five lines; the reason it works is an argument about cancelling pairs, and the interviewer wants the argument.

The problem it solves

Given an array of n values, return the value that appears more than n / 2 times. For [2, 2, 1, 3, 2, 2, 2] the answer is 2, which fills five of seven slots. The common version promises that a majority exists; a stricter version asks you to report when it does not.

There are three obvious approaches, and each costs something:

• Count with a hash map. O(n) time, but O(n) extra space in the worst case, one entry per distinct value.
• Sort and take the middle. A majority must cover index n // 2 of the sorted array. O(n log n) time, and the sort either needs a copy or destroys the input.
• Check every value against every other. O(n²), the brute force worth naming and then leaving behind.

Boyer-Moore gets O(n) time and two variables.

The intuition

Pair up values that differ and throw each pair away. If one value fills more than half the array, it cannot be fully paired off: there are not enough other values to cancel all of its copies. Whatever survives the cancelling must be the majority, if there is one.

The algorithm does that pairing on the fly. It keeps a candidate and a count:

• When the count is zero, the next value becomes the candidate.
• A value equal to the candidate adds one.
• A different value subtracts one: it cancels against one copy of the candidate.

The key moment is the count returning to zero. At that point the stretch scanned so far splits exactly in half between the candidate and everything else. Discarding that stretch removes at most half of any value's copies, so a true majority of the whole array is still a majority of what remains. The scan simply starts over on the rest.

Notice what the argument does not prove. The survivor is the only value that could be a majority. If no majority exists, something still survives. On [1, 2, 3] the candidate ends as 3, and 3 appears once. That is why the strict version needs a second pass to count the candidate. Skipping it is the most common mistake.

Watch it run

The animation runs the lesson's array, [2, 2, 1, 3, 2, 2, 2], holding one candidate and one count, where every disagreement cancels a pair. The count starts at zero, so 2 takes the floor as the new candidate. The second 2 agrees, and the count rises to 2. Then 1 disagrees and cancels one vote, leaving 1, and 3 disagrees too, bringing the count back to zero. Everything up to there cancels out and goes grey, so the majority of the rest is the majority of the whole. The next 2 takes the floor again, and the last three values push the count to 3. The 2 survived every cancellation: one pass, two variables, then one recount to prove it really is a majority.

The code

The lesson's loop, split into the candidate pass and the recount:

def majority_candidate(nums):
    candidate, count = None, 0
    for x in nums:
        if count == 0:                   # nobody holds the floor
            candidate = x
        count += 1 if x == candidate else -1
    return candidate

def majority(nums):
    c = majority_candidate(nums)
    return c if nums.count(c) * 2 > len(nums) else None   # the recount

print(majority([2, 2, 1, 3, 2, 2, 2]))            # 2
print(majority([3, 3, 4]))                        # 3
print(majority([1, 2, 3]))                        # None
print(majority_candidate([1, 2, 3]))              # 3   a survivor, not a majority

The state after each value, matching the animation frame by frame as (value, candidate, count):

def trace(nums):
    candidate, count, log = None, 0, []
    for x in nums:
        if count == 0:
            candidate = x
        count += 1 if x == candidate else -1
        log.append((x, candidate, count))
    return log

for row in trace([2, 2, 1, 3, 2, 2, 2]):
    print(row)
# (2, 2, 1)
# (2, 2, 2)
# (1, 2, 1)
# (3, 2, 0)
# (2, 2, 1)
# (2, 2, 2)
# (2, 2, 3)

The common follow-up asks for every value that appears more than n / 3 times. At most two values can, so keep two candidates and cancel triples of distinct values instead of pairs, then recount both:

def more_than_third(nums):
    c1, c2, n1, n2 = None, None, 0, 0
    for x in nums:
        if x == c1:
            n1 += 1
        elif x == c2:
            n2 += 1
        elif n1 == 0:
            c1, n1 = x, 1
        elif n2 == 0:
            c2, n2 = x, 1
        else:
            n1, n2 = n1 - 1, n2 - 1      # cancel a triple
    return sorted(c for c in {c1, c2}
                  if c is not None and nums.count(c) * 3 > len(nums))

print(more_than_third([3, 2, 3]))                 # [3]
print(more_than_third([1, 1, 1, 3, 3, 2, 2, 2]))  # [1, 2]

Both functions against a Counter on 5,000 random arrays, half of them with a planted majority:

from collections import Counter
import random

random.seed(19)
ok = True
for _ in range(5000):
    n = random.randint(1, 30)
    nums = [random.randint(0, 3) for _ in range(n)]
    if random.random() < 0.5:                     # plant a real majority half the time
        v = random.randint(0, 3)
        nums += [v] * (n + 1)
        random.shuffle(nums)
    counts = Counter(nums)
    want = next((v for v, k in counts.items() if k * 2 > len(nums)), None)
    ok &= majority(nums) == want
    ok &= more_than_third(nums) == sorted(v for v, k in counts.items() if k * 3 > len(nums))
print(ok)                                         # True

The complexity

• Time: O(n) for the candidate pass, plus O(n) for the recount. Two passes, still linear.
• Space: O(1). A candidate and a count, or two of each for the n / 3 version.
• Compared with the hash map: same time, but the map can grow to n entries. On a stream too large to hold, the voting pass is the one that fits.
• Generalised: for more than n / k occurrences, keep k - 1 candidates. Time becomes O(n·k) and space O(k).

Where it goes wrong

• Skipping the recount when the input does not promise a majority. The survivor of [1, 2, 3] is 3, and 3 is not a majority.
• Updating the count before choosing the candidate. Check for zero first, then compare; the other order compares against a stale candidate.
• Using "at least half" instead of "more than half". In [1, 1, 2, 2] no value is a majority, and a recount with >= would wrongly accept one.
• In the n / 3 version, checking n1 == 0 before x == c2. The matches must be tested first, or the same value can end up held as both candidates.
• Claiming the survivor is the most frequent value. Without a majority, it can be any value at all.

When it shows up in interviews

It is a standard easy question whose real test is the follow-up: "can you do it in constant space?" Expect to be asked why the cancelling works, what happens when no majority exists, and how to extend it to n / 3. It also appears inside streaming questions, where a single pass with fixed memory is the whole point, and it is a good warm-up before two-pointer and prefix-sum array problems.

How to say it in an interview

"A hash map works in linear time and linear space, but I can do it in constant space with Boyer-Moore voting. I keep a candidate and a count. When the count is zero I adopt the current value; a match adds one and a mismatch subtracts one. Each mismatch cancels a pair of different values, and a value that fills more than half the array cannot be cancelled completely, so it must be the survivor. Whenever the count returns to zero, the prefix splits evenly, so the majority of the rest is the majority of the whole. The survivor is only a candidate, so if a majority is not guaranteed I recount it in a second pass. Linear time, constant space."