Lesson 7 — Boyer-Moore Majority Vote

~20 minutes · the cancellation invariant · Python

Tonight's problem is Majority Element. The interview version sounds almost too simple: return the value that appears more than half the time. The trap is that the obvious counting ideas either re-scan too much or store more than you need. Boyer-Moore teaches one sharper move: cancel opposite votes until only the real majority can survive.

The invariant

A true majority survives pairwise cancellation; when the count hits zero, adopt a new candidate.

That's the whole idea. If one value appears more than half the time, every non-majority value can be paired against one majority value and discarded. There still must be at least one majority vote left over. The Boyer-Moore majority vote algorithm turns that cancellation into one pass with two variables.

Cancellation removes one majority vote with one opposing vote; the majority still has votes left.

Majority Element: the slow way first

The LeetCode statement guarantees that the majority element exists and appears more than floor(n / 2) times. The direct brute force approach is to count each value by scanning the whole list:

def majority_element(nums):
    for x in nums:
        count = 0
        for y in nums:                 # re-scan the whole list
            if y == x:
                count += 1
        if count > len(nums) // 2:
            return x

This works, but it is O(n^2): for every possible answer, it scans the array again. You can also use a hash map in O(n) time and O(n) space, but the guarantee lets us do better on memory.

Majority Element: the cancellation way

Keep a candidate and a count. The count is not the candidate's total frequency. It is the candidate's current pile of unmatched votes after cancellation.

def majority_element(nums):
    candidate = None
    count = 0
    for x in nums:
        if count == 0:
            candidate = x              # adopt a fresh candidate
        if x == candidate:
            count += 1                 # same vote supports it
        else:
            count -= 1                 # different vote cancels one
    return candidate                   # majority is guaranteed

Notice the order: when the count has fallen to zero, the current value becomes the new candidate before this vote is processed. That gives the new candidate one unmatched vote to stand on.

The zeroes mark the reset points: the next scanned value becomes the fresh candidate before its vote is counted.

Transfer: same vote, new costume

A live poll receives reactions like ["red", "blue", "red", "red", "green"]. One reaction is guaranteed to appear more than half the time. Return that reaction, using constant space.

Before reading on: predict the two variables you would carry, and what should happen when the count becomes zero.

def winning_reaction(reactions):
    candidate = None
    count = 0
    for reaction in reactions:
        if count == 0:
            candidate = reaction
        count += 1 if reaction == candidate else -1
    return candidate

What the trade buys you

The win is not just speed. It is also memory: one candidate, one count, one pass.

Practice — answer before you scroll past

candidate = None
count = 0
for x in nums:
    if x == candidate:
        count += 1
    else:
        count -= 1
    if count == 0:
        candidate = x

Your move (tonight)

Solve this on LeetCode, logging it in your Notion tracker with the cycle — predict → attempt → compare → encode:

1. Majority Element — first say the brute force and its complexity out loud, then code Boyer-Moore from the invariant.

For the encode step, write the invariant at the top of this page in your own words. Revision days test that sentence, not a memorized code shape.

Primary source

Stuck or curious? Ask your teacher (the agent) — that's what it's for.