Boyer-Moore Majority Vote: O(1) Space and the Follow-ups

"Find the element that appears more than n/2 times" looks like a hash-map counting problem. The answer interviewers are hoping for uses O(1) extra space: the Boyer-Moore majority vote.

The algorithm

def majority(nums):
    cand, count = None, 0
    for x in nums:
        if count == 0:
            cand = x
        count += 1 if x == cand else -1
    return cand

Why it works

Think of it as pairing off different elements and cancelling them. Each decrement removes one copy of the candidate and one copy of something else. A true majority has more copies than everything else combined, so it can't be fully cancelled and must be the survivor.

The verification pass

If the input is not guaranteed to have a majority, the survivor may be wrong ([1, 2, 3] returns 3). Do a second pass to count the candidate and check count > n // 2. Mentioning this unprompted is a strong signal.

Generalisation: elements above n/3

At most two elements can appear more than n/3 times, so keep two candidates and two counters:

def majority_n3(nums):
    c1, c2, k1, k2 = None, None, 0, 0
    for x in nums:
        if x == c1: k1 += 1
        elif x == c2: k2 += 1
        elif k1 == 0: c1, k1 = x, 1
        elif k2 == 0: c2, k2 = x, 1
        else: k1 -= 1; k2 -= 1
    return [c for c in (c1, c2)
            if c is not None and nums.count(c) > len(nums) // 3]

In general, more-than-n/k needs k−1 candidates (the Misra-Gries summary), which is also the basis of heavy-hitter detection in streaming systems.

Where else it appears

• Streaming: find frequent items in one pass with bounded memory.
• Distributed: run it per shard, then merge the candidates and verify globally.

Summary: "Cancel pairs of different values; the majority survives; verify with a second pass if it isn't guaranteed."

Disclosure: written by people building a real-time AI interview helper (Linkjob AI).