Majority Element: Boyer-Moore Voting Algorithm

LeetCode Majority Element (problem 169) asks a simple question: given an array nums of size n, return the element that appears more than n / 2 times. You are guaranteed that a majority element always exists.

Sounds easy enough. And it is, if you are fine with a hash map or sorting. But there is a solution that runs in O(n) time and O(1) space, and it uses one of the most elegant algorithms in computer science: the Boyer-Moore voting algorithm.

Let's start with what the problem looks like, then work through three approaches.

The problem

Given nums = [2, 2, 1, 1, 2, 2, 2], return 2. The number 2 appears 5 times out of 7, which is more than half.

The majority element is guaranteed to exist. That constraint is important because it means you do not need to verify your answer (though in a real-world scenario, you would).

Approach 1: Hash map (frequency counter)

The most natural approach. Count how many times each element appears, then return the one with a count greater than n / 2.

def majority_element(nums: list[int]) -> int:
    counts = {}
    for num in nums:
        counts[num] = counts.get(num, 0) + 1
        if counts[num] > len(nums) // 2:
            return num
    return -1

Walk through the array once, incrementing counts. The moment any count exceeds n / 2, return that element immediately. You do not even need to finish the loop.

This works perfectly. O(n) time, O(n) space. For most interview situations, this is a solid first answer.

Approach 2: Sort and pick the middle

If you sort the array, the majority element will always occupy the middle position. Think about it: if an element appears more than half the time, it has to span the midpoint no matter how the other elements are arranged.

def majority_element(nums: list[int]) -> int:
    nums.sort()
    return nums[len(nums) // 2]

Two lines. O(n log n) time, O(1) space if you sort in place. This is a perfectly valid solution, and some interviewers appreciate how clean it is. But it modifies the input array and is slower than O(n).

Approach 3: Boyer-Moore voting algorithm (optimal)

Here is where it gets interesting. The Boyer-Moore voting algorithm finds the majority element in a single pass using only two variables: a candidate and a count. No hash map, no sorting, no extra memory.

The idea is simple but not obvious. You walk through the array and maintain a running "election." The candidate starts as the first element with a count of 1. For each subsequent element:

• If it matches the candidate, increment the count (a "vote" for the candidate).
• If it does not match, decrement the count (a "vote against").
• If the count hits 0, the next element becomes the new candidate with a count of 1.

At the end, the candidate is the majority element.

def majority_element(nums: list[int]) -> int:
    candidate = nums[0]
    count = 0
    for num in nums:
        if count == 0:
            candidate = num
        count += 1 if num == candidate else -1
    return candidate

O(n) time. O(1) space. That is the best you can possibly do for this problem.

Visual walkthrough: Boyer-Moore voting step by step

Let's trace through nums = [2, 2, 1, 1, 2, 2, 2] to see exactly how the candidate and count evolve.

The key insight is that every non-majority element can "cancel out" at most one occurrence of the majority element. But since the majority element has more than n/2 occurrences, it can never be fully canceled. It always survives as the final candidate.

Why does Boyer-Moore work?

It helps to think about it mathematically. The majority element appears more than n / 2 times. Every other element combined appears fewer than n / 2 times. So if you pair up each minority element with a majority element (the "canceling" that happens when count decrements), you run out of minority elements before you run out of majority elements.

That is the whole proof. The majority element survives because it outnumbers everything else combined.

One thing to note: if the problem did NOT guarantee a majority element exists, you would need a second pass to verify the candidate actually appears more than n / 2 times. The algorithm only finds a candidate. The guarantee is what lets us skip verification.

Complexity comparison

*Python's sort() is in-place, but technically uses O(log n) stack space internally.

Boyer-Moore wins on every dimension. Same linear time as the hash map approach, but with constant space and no input modification. In an interview, start with the hash map solution, then offer Boyer-Moore as the optimization.

The building blocks

This problem breaks down into one core reusable piece that CodeBricks drills independently:

Frequency counter

The act of counting how often each element appears in a collection. In the hash map approach, you build a dictionary of counts. In Boyer-Moore, you are doing a compressed version of the same thing: tracking the "net count" of the leading element.

counts = {}
for item in collection:
    counts[item] = counts.get(item, 0) + 1

This frequency counter brick shows up everywhere:

• Group Anagrams: count character frequencies to generate a key
• Valid Anagram: compare frequency counts of two strings
• Top K Frequent Elements: count frequencies, then extract the top K
• First Unique Character: count frequencies, then find the first with count 1

The Boyer-Moore algorithm itself is more specialized, but the frequency-counting mental model behind it is universal. When a problem asks "which element appears most/least" or "how many times does X appear," you are reaching for the frequency counter brick.

Common mistakes

1. Forgetting the guarantee. Boyer-Moore only works when a majority element is guaranteed to exist. If it is not guaranteed, you need a verification pass. Some interviewers will test whether you know this.

2. Off-by-one on the threshold. The majority element appears more than n / 2 times, not n / 2 or more. For n = 6, it must appear at least 4 times, not 3. In practice this rarely changes the answer, but it matters for edge cases.

3. Initializing count to 1 instead of 0. If you set count = 1 and candidate = nums[0], then start your loop from index 1, that works too. But mixing up the initialization with the "check if count is 0" logic is a common source of bugs. The cleanest version initializes count to 0 and lets the if count == 0 block handle the first element naturally.

When to use Boyer-Moore

The Boyer-Moore voting algorithm is specific to the majority element problem. You will not use it on most LeetCode problems. But recognizing when it applies is valuable:

• The problem explicitly asks for an element appearing more than n/2 times
• You need O(1) space and the input has a dominance guarantee
• A follow-up asks "can you do it without extra memory?"

For problems that ask about elements appearing more than n / 3 times (like Majority Element II), you can extend Boyer-Moore to track two candidates instead of one. Same principle, slightly more bookkeeping.

Related posts

• Hash Map Patterns - The frequency counter pattern used in Approach 1 is one of the three core hash map techniques
• Contains Duplicate - Another "easy" array problem where the hash-based approach dominates
• Group Anagrams - Uses frequency counting as a grouping key, a more advanced application of the same brick

The frequency counter is one of those building blocks that feels trivially simple in isolation. You count things. That is it. But when you need it under pressure in a new context, the difference between "I vaguely remember counting" and "my fingers automatically write the counting loop" is the difference between stumbling and solving. Spaced repetition gets you to the automatic stage.