Majority Element and Boyer-Moore Voting

A majority element is a value that occurs more than n/2 times in an array of length n. Counting with a hash map finds it in O(n) time and O(n) memory, and sorting finds it in O(n log n), but the Boyer-Moore majority vote algorithm needs one pass and two variables. Its "cancel out different values" idea generalizes to finding every value above n/k with k - 1 counters, which is the standard answer to "frequent items in a stream".

Intuition

Pair up occurrences of different values and throw each pair away. A value that occurs more than half the time cannot be fully cancelled: even if every other element is paired against it, some copies are left over. So whatever survives the cancellation is the only possible majority.

Boyer-Moore does the cancellation in a single pass with a candidate and a counter:

• When the counter is 0, the current element becomes the new candidate.
• An element equal to the candidate increments the counter; a different element decrements it (one copy of the candidate and this element cancel).

At the end the candidate is the majority if one exists. If none exists, the candidate is arbitrary, so a second pass must count it whenever the input is not guaranteed to contain a majority.

The same argument works for any threshold. Removing k distinct values at once can remove at most one copy of each value, so a value with more than n/k copies survives. Keeping k - 1 candidates with counters (the Misra-Gries algorithm) implements this; with k = 3 that is two candidates, the "more than n/3" question.

When to use it in interviews / OAs

• "Find the element that appears more than n/2 times" with an O(1) extra space follow-up.
• "Find all elements that appear more than n/3 times": at most two can exist; use two candidates.
• Streaming or memory-limited settings: heavy hitters in logs or network traffic, more-than-n/k items with k - 1 counters.
• Verifying that a "dominant" value exists before using it, for example the dominant index of an array or the minimum index of a valid split.

Template

Boyer-Moore majority vote

def majority_element(nums: list[int]) -> int | None:
    """The value occurring more than len(nums) // 2 times, or None if there is none."""
    candidate, count = None, 0
    for x in nums:
        if count == 0:
            candidate = x  # nothing left to cancel: start over with x
        count += 1 if x == candidate else -1  # a different value cancels one copy
    if nums and nums.count(candidate) * 2 > len(nums):  # verify: needed when no majority is guaranteed
        return candidate
    return None

More than n/3: two candidates

def elements_above_third(nums: list[int]) -> list[int]:
    """All values occurring more than len(nums) // 3 times (there are at most two)."""
    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:  # x and one copy of each candidate: three distinct values cancel
            n1 -= 1
            n2 -= 1
    return [c for c in (c1, c2) if c is not None and nums.count(c) * 3 > len(nums)]

The order of the branches matters: check "equals a candidate" before "a counter is empty", otherwise the same value can occupy both slots.

More than n/k: Misra-Gries heavy hitters

def heavy_hitters(nums: list[int], k: int) -> list[int]:
    """All values occurring more than len(nums) / k times, using at most k - 1 counters."""
    counters: dict[int, int] = {}
    for x in nums:
        if x in counters:
            counters[x] += 1
        elif len(counters) < k - 1:
            counters[x] = 1
        else:  # x plus one copy of every candidate: k distinct values cancel
            for key in list(counters):
                counters[key] -= 1
                if counters[key] == 0:
                    del counters[key]
    return [c for c in counters if nums.count(c) * k > len(nums)]

Every decrement cancels a copy that was counted earlier, so the decrement loops cost O(n) in total.

Complexity

• majority_element: O(n) time, O(1) extra space (two passes).
• elements_above_third: O(n) time, O(1) extra space.
• heavy_hitters: O(n) amortized for the scan with O(k) memory; the verification as written costs O(n * k), or O(n) with one counting pass over the surviving candidates.
• Alternatives worth naming: a hash map count (O(n) time and space), sorting and taking the middle element (O(n log n)), quickselect for the median (expected O(n), since a majority must be the median), random sampling (pick a random element and check it; expected fewer than two tries when a majority exists), and per-bit voting (each bit of the majority is the majority bit at that position).

Common pitfalls

• Skipping verification when the problem does not promise that a majority exists. The vote always returns some candidate.
• Using >= instead of >. Exactly n/2 copies is not a majority; for n = 4, [1, 1, 2, 2] has none.
• Branch order in the two-candidate version, as noted above.
• Initializing both candidates to the same value (for example 0): if 0 really occurs, it can be counted in the wrong slot. Use None or distinct sentinels.
• Assuming the vote finds the most frequent element. Without a majority the candidate may not be the mode at all; for the mode in general you need counting.

Interview variations

• Majority element (guaranteed to exist): the vote alone, no verification.
• Majority element II (more than n/3): two candidates plus verification.
• Check whether a target is the majority in a sorted array: binary search for its first occurrence and check the element n/2 positions later.
• Minimum index of a valid split: the dominant element of the whole array must be dominant on both sides; count prefix occurrences of the single candidate.
• Online majority queries on subarrays are much harder (segment tree of vote candidates plus occurrence lists for verification), usually beyond interview scope.