DSA Majority Element by Voting (Boyer–Moore)

The problem

A majority element appears more than half the times in a list. The Majority Vote problem asks for that element. A list with no such element answers None.

More than half is strict. An element in exactly half the places is not a majority. The cases below include one list with no majority.

cases = [
    ([3, 3, 4, 2, 3, 3, 1], 3),
    ([2, 2, 1, 1, 1, 2, 2], 2),
    (["Mia", "Leo", "Mia", "Ana", "Mia"], "Mia"),
    ([1, 2, 3, 2, 1], None),
]
for values, expected in cases:
    print("list", values, "majority:", expected)

Read the second row by counting. The value 2 appears four times in seven places. Four is more than half of seven.

Intuition: cancel one vote against one opposing vote

Pair one copy of a value with one copy of a different value. Both copies in the pair cancel out. A true majority has more copies than all other values combined, so it survives every cancellation.

values = [2, 2, 1, 2, 3, 2]
candidate = None
count = 0
for value in values:
    if count == 0:
        candidate = value
        count = 1
    elif value == candidate:
        count += 1
    else:
        count -= 1
    print(value, "-> candidate", candidate, "count", count)
print("survivor:", candidate, "real count:", values.count(candidate), "of", len(values))

The counter falls whenever an unlike value lands. It never falls below the majority's true lead for long. The survivor here is 2, and its real count confirms the lead.

Brute force: count every value with a full scan

The brute force counts each distinct value by scanning the whole list. The first value whose count passes half wins. Scans repeat for every distinct value, and a counter records the comparisons.

def majority_brute(values):
    checked = []
    comparisons = 0
    for value in values:
        if value in checked:
            continue
        checked.append(value)
        seen = 0
        for other in values:
            comparisons += 1
            if other == value:
                seen += 1
        if seen * 2 > len(values):
            return value, comparisons
    return None, comparisons

cases = [
    [3, 3, 4, 2, 3, 3, 1],
    [1, 2, 3, 2, 1],
    [5, 5, 5, 5],
]
for values in cases:
    result, comparisons = majority_brute(values)
    print("list", values, "->", result, "comparisons:", comparisons)

The no-majority row is the expensive one. It pays a full scan for each distinct value, and it still finds nothing. Voting keeps the same answer with one counter.

The optimal solution: vote, then verify the survivor

The voting method keeps one candidate and one counter, raising the counter on a match, lowering it on a mismatch, and replacing the candidate whenever the counter is empty. A counting pass then verifies the survivor.

The verification pass is not optional. A candidate can survive voting on a list with no majority. Only its real count decides the answer.

def vote(values):
    candidate = None
    count = 0
    for value in values:
        if count == 0:
            candidate = value
            count = 1
        elif value == candidate:
            count += 1
        else:
            count -= 1
    return candidate

def by_voting(values):
    if not values:
        return None
    candidate = vote(values)
    seen = 0
    for value in values:
        if value == candidate:
            seen += 1
    if seen * 2 > len(values):
        return candidate
    return None

cases = [
    ([3, 3, 4, 2, 3, 3, 1], 3),
    ([2, 2, 1, 1, 1, 2, 2], 2),
    (["Mia", "Leo", "Mia", "Ana", "Mia"], "Mia"),
    ([1, 2, 3, 2, 1], None),
]
for values, expected in cases:
    result = by_voting(values)
    print("list", values, "->", result, "expected:", expected, "match:", result == expected)

All four cases from the start of the article pass. The no-majority row survives voting with candidate 1. Verification rejects it, because 1 appears only twice in five places.

Walkthrough: voting on [3, 3, 4, 2, 3, 3, 1]

The walk prints the candidate and the counter after each value. It then runs the verification count on the survivor.

values = [3, 3, 4, 2, 3, 3, 1]
candidate = None
count = 0
for value in values:
    if count == 0:
        candidate = value
        count = 1
    elif value == candidate:
        count += 1
    else:
        count -= 1
    print("value", value, "-> candidate", candidate, "count", count)
seen = 0
for value in values:
    if value == candidate:
        seen += 1
print("verification: candidate", candidate, "appears", seen, "of", len(values))
print("more than half:", seen * 2 > len(values))

The counter ends at 1, but that number is not the count of 3. Verification counts four copies of 3 in seven places. The answer is read off the verification, not off the counter.

Complexity

Voting makes one pass and verification makes one more, so the time is O(n) for n values. Voting holds one candidate and one counter, so its extra space is O(1).

def brute_comparisons(values):
    checked = []
    comparisons = 0
    for value in values:
        if value in checked:
            continue
        checked.append(value)
        for other in values:
            comparisons += 1
            if other == value:
                pass
    return comparisons

for n in [7, 14, 28]:
    values = list(range(n))
    print("values", n, "- brute comparisons:", brute_comparisons(values), " voting plus verify steps:", 2 * n)

The brute list here holds all distinct values, its worst case. Its comparisons grow with the square of the length. The two voting passes grow in a straight line.

Edge cases and pitfalls

An empty list has no majority. A single value is its own majority, because one is more than half of one. Exactly half is the trap case, and it answers None.

def vote(values):
    candidate = None
    count = 0
    for value in values:
        if count == 0:
            candidate = value
            count = 1
        elif value == candidate:
            count += 1
        else:
            count -= 1
    return candidate

def by_voting(values):
    if not values:
        return None
    candidate = vote(values)
    seen = 0
    for value in values:
        if value == candidate:
            seen += 1
    if seen * 2 > len(values):
        return candidate
    return None

print("empty list:", by_voting([]))
print("single value:", by_voting([9]))
print("all the same:", by_voting([5, 5, 5, 5]))
print("exactly half:", by_voting([1, 1, 2, 2]))
print("survivor without majority:", vote([1, 2, 3, 2, 1]), "verdict:", by_voting([1, 2, 3, 2, 1]))
print("leader changes late:", by_voting([1, 1, 2, 2, 2]))

The skipped verification is the classic pitfall. The survivor row shows a candidate standing after voting on a list with no winner. Declaring it the answer would be wrong.