Majority Element — Boyer-Moore Voting Algorithm Explained Deeply [LeetCode 169]

Problem Statement

Given an array nums of size n, return the majority element. The majority element is the element that appears more than ⌊n/2⌋ times. You may assume that the majority element always exists in the array.

Example 1:

Input:  nums = [3, 2, 3]
Output: 3
Explanation: 3 appears 2 times out of 3 elements (> 3/2 = 1.5). It is the majority.

Example 2:

Input:  nums = [2, 2, 1, 1, 2, 2, 1]
Output: 2
Explanation: 2 appears 4 times out of 7 elements (> 7/2 = 3.5). It is the majority.

The guarantee matters: The problem guarantees a majority always exists. This is not a search problem — it is a survivor-finding problem. That distinction will drive the most elegant solution.

• Why This Problem Matters
• Four Approaches
• Boyer-Moore Deep Dive
• The Election Metaphor
• The Mechanics
• Why It Feels Wrong (Until It Clicks)
• Why Boyer-Moore Is Correct — The Proof Sketch
• Visual Dry Run
• Common Mistakes
• Solutions
• Approach 1 — Brute Force O(n²) / O(1)
• Approach 2 — HashMap O(n) / O(n)
• Approach 3 — Sort O(n log n) / O(1)
• Approach 4 — Boyer-Moore Voting O(n) / O(1) — Optimal
• Complexity Analysis
• Approach 1 — Brute Force
• Approach 2 — HashMap
• Approach 3 — Sort
• Approach 4 — Boyer-Moore (Optimal)
• Follow-up Questions
• Majority Element II — LeetCode 229
• Streaming Input
• This Pattern Solves
• Key Takeaway

Why This Problem Matters

This problem appears in Google, Amazon, Meta, and Microsoft interviews at all levels. But the real reason it is worth studying deeply is not its frequency — it is the algorithm behind its optimal solution.

The Boyer-Moore Voting Algorithm was published in 1981 by Robert S. Boyer and J Strother Moore. It is classified as a streaming algorithm: it makes a single pass through the data, uses only O(1) extra memory, and solves a problem that naively feels like it requires remembering everything. That combination is extraordinarily rare and valuable.

When you encounter this problem in an interview, the hashmap solution will be your safe option, and the Boyer-Moore solution will be your showcase move. Interviewers who ask this problem almost always follow up with "can you do it in O(1) space?" — and they want to hear not just the code, but the intuition behind why it works.

Beyond interview performance, the Boyer-Moore algorithm is a prototypical example of a cancellation-based approach — a family of algorithms that can solve problems in one pass by intelligently destroying information rather than accumulating it. Recognizing this pattern opens up problems like Majority Element II, weighted voting systems, and streaming statistics.

Four Approaches

Before we dive deep, here is the landscape of all four approaches and their trade-offs:

*Sorting in-place avoids extra space but modifies the original array — often not acceptable.

Interview rule of thumb: Start by describing all four approaches with their complexities. Show the interviewer you understand the solution space. Then implement Boyer-Moore and explain the intuition. If you can articulate why it is correct without hand-waving, you will stand out.

Boyer-Moore Deep Dive

Let's build the algorithm from scratch using a metaphor that makes the intuition stick.

The Election Metaphor

Imagine you are counting votes in an election. There are many candidates, but one candidate — the majority candidate — has received more than half of all votes cast.

Now imagine an extreme counting rule: if two voters voted for different candidates, their votes cancel each other out and both are eliminated from the count. You keep cancelling pairs of different votes until either no votes remain, or everyone left voted for the same candidate.

Ask yourself: who survives?

The majority candidate always survives. Here is why: they received more than n/2 votes. The opposition — combined — received fewer than n/2 votes. Even in the worst case, where every opposition vote cancels exactly one majority vote, the opposition runs out of votes first. The majority candidate is left standing with at least one vote remaining.

That is the entire Boyer-Moore Voting Algorithm. It simulates this cancellation without actually storing any votes.

The Mechanics

The algorithm maintains two variables:

• candidate — the current "surviving" element
• count — how many more times we have seen candidate than anything else in the current window

Walk through the array element by element:

1. If count == 0: the previous candidate was fully cancelled. Adopt the current element as the new candidate. Reset count = 1.
2. If current == candidate: this vote reinforces the candidate. Increment count.
3. Otherwise: this vote cancels one candidate vote. Decrement count.

At the end of the array, candidate holds the majority element.

The critical and counterintuitive insight: we never explicitly track what cancelled what. We lose information by design — and that is what makes it O(1) space. The algorithm bets on the mathematical guarantee: the majority cannot be cancelled to zero. If the problem guarantees a majority exists (as LeetCode 169 does), the final candidate is guaranteed to be correct without any verification pass.

Why It Feels Wrong (Until It Clicks)

The algorithm resets the candidate mid-array. When count drops to zero, we throw away the current candidate and start fresh. This feels dangerous — what if we threw away the majority element?

We cannot. Think about it: for count to reach zero, the current candidate was seen exactly as many times as everything else combined in that prefix. If the candidate was the majority element, it used up an equal number of non-majority elements to cancel itself to zero. But the majority element still has more than half the remaining array ahead of it. It will win again.

Conversely, if the candidate was not the majority element, throwing it away costs nothing — we needed to discard it anyway.

Either way, resetting is safe.

Why Boyer-Moore Is Correct — The Proof Sketch

Let M be the majority element. By definition, M appears more than n/2 times in the array of n elements.

Consider every decrement operation (when current != candidate). Each decrement represents a cancellation event: one current element and one candidate element are "paired" and effectively eliminated from the count. Crucially, each cancellation consumes at most one instance of M (when M is the current candidate being decremented against) or zero instances of M (when some other element is the candidate).

For M to be eliminated as the final candidate, it would need to be cancelled as many times as it appears. Each cancellation of M requires one non-M element to be consumed. Since there are fewer than n/2 non-M elements, and M appears more than n/2 times, there are not enough non-M elements to fully cancel M.

More formally: the loop invariant maintained by Boyer-Moore is that after processing k elements, the sequence partitions into (k - count) / 2 pairs of distinct cancelled elements, plus count copies of the current candidate. This invariant proves that if a majority element exists, it can only be the final candidate at the end of the array.

The algorithm does not find the majority element by eliminating others. It finds it by being the last one that cannot be eliminated.

Visual Dry Run

Let's trace nums = [2, 2, 1, 1, 2, 2, 1] step by step.

Initial state: candidate = None, count = 0

Step 1 — num = 2
  count == 0 → adopt new candidate
  candidate = 2, count = 1

Step 2 — num = 2
  2 == candidate (2) → reinforce
  candidate = 2, count = 2

Step 3 — num = 1
  1 != candidate (2) → cancel
  candidate = 2, count = 1

Step 4 — num = 1
  1 != candidate (2) → cancel
  candidate = 2, count = 0

Step 5 — num = 2
  count == 0 → adopt new candidate
  candidate = 2, count = 1

  (Note: count was 0, so we reset — but we coincidentally re-adopt 2.
   If this had been a 3 here, candidate would have become 3.
   The algorithm still would have been correct: 2 will win later.)

Step 6 — num = 2
  2 == candidate (2) → reinforce
  candidate = 2, count = 2

Step 7 — num = 1
  1 != candidate (2) → cancel
  candidate = 2, count = 1

Final: candidate = 2, count = 1 → return 2 ✓

Notice that at step 4, count reached zero and the candidate was reset. The majority element (2) "survived" this reset because it appeared again immediately at step 5. The non-majority elements exhausted themselves trying to cancel 2 — and failed.

Common Mistakes

1. Ignoring the majority guarantee and adding a verification pass anyway.

The problem guarantees a majority always exists. A verification pass (a second O(n) scan to count the candidate's occurrences) is only necessary when the problem does not guarantee a majority — for example, in a general "find the most frequent element" problem. Adding an unnecessary verification pass in this specific problem is harmless, but mentioning it signals to the interviewer that you understand when the guarantee matters versus when it does not. Say: "Since the problem guarantees a majority exists, we can skip the verification pass. If the guarantee were absent, we'd add one."

2. Incorrect reset logic — setting count = 0 instead of 1 when adopting a new candidate.

A very common bug: when count reaches zero, some candidates write candidate = num; count = 0 and then rely on the next iteration's increment. This either skips the current element entirely or produces an off-by-one. The correct logic is to adopt the current element and immediately set count = 1, treating the current element as the first "vote" for the new candidate.

3. Presenting only Boyer-Moore without discussing trade-offs.

In real interviews, jumping straight to the O(1) space solution without acknowledging alternatives can look like pattern-matching rather than reasoning. Interviewers want to see you know why you chose Boyer-Moore. Say: "The hashmap approach is the safe O(n)/O(n) solution — easy to implement and easy to verify. Boyer-Moore is the optimal solution when we cannot afford extra space, but it requires understanding the correctness guarantee. Given that this problem guarantees a majority exists, I'll implement Boyer-Moore and explain why it works."

4. Not recognizing when the sort approach is acceptable.

The sort solution — sort the array, return nums[n//2] — is O(n log n) time but O(1) space (in-place sort). It works because the majority element, appearing more than n/2 times, is guaranteed to occupy the middle index after sorting. This is a perfectly valid interview answer when O(n log n) is acceptable and you need to communicate a clean, obvious-correctness solution quickly. Do not dismiss it — know when to use it.

Solutions

Approach 1 — Brute Force O(n²) / O(1)

For each element, count how many times it appears. Return when count exceeds n/2.

Python

from typing import List

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        n = len(nums)

        for i in range(n):
            count = 0
            # Count occurrences of nums[i] in the entire array
            for j in range(n):
                if nums[j] == nums[i]:
                    count += 1

            # If this element appears more than n/2 times, it is the majority
            if count > n // 2:
                return nums[i]

        # Problem guarantees a majority exists — this is unreachable
        return -1

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
function majorityElement(nums) {
    const n = nums.length;

    for (let i = 0; i < n; i++) {
        let count = 0;

        // Count occurrences of nums[i] across the full array
        for (let j = 0; j < n; j++) {
            if (nums[j] === nums[i]) count++;
        }

        // Majority element appears more than floor(n/2) times
        if (count > Math.floor(n / 2)) return nums[i];
    }

    // Unreachable — the problem guarantees a majority always exists
    return -1;
}

Approach 2 — HashMap O(n) / O(n)

Count every element's frequency in one pass. Return the element whose frequency exceeds n/2.

Python

from typing import List
from collections import Counter

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        # Count frequencies of all elements in a single pass
        freq = Counter(nums)
        n = len(nums)

        # The majority element appears more than n//2 times
        # Counter.most_common(1) returns [(element, count)] sorted by frequency
        for element, count in freq.items():
            if count > n // 2:
                return element

        # Problem guarantees a majority — this is unreachable
        return -1

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
function majorityElement(nums) {
    const freq = new Map();
    const n = nums.length;

    for (const num of nums) {
        // Accumulate frequency count for each element
        freq.set(num, (freq.get(num) || 0) + 1);

        // Early exit: as soon as any element's count exceeds n/2, return it
        if (freq.get(num) > Math.floor(n / 2)) return num;
    }

    // Unreachable — the problem guarantees a majority always exists
    return -1;
}

Approach 3 — Sort O(n log n) / O(1)

Sort the array. The element at the middle index is always the majority element, because a majority element (appearing more than n/2 times) must span across the center of any sorted array.

Python

from typing import List

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        # After sorting, the majority element always occupies index n//2.
        # Proof: it appears > n/2 times, so it must cover the midpoint.
        nums.sort()
        return nums[len(nums) // 2]

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
function majorityElement(nums) {
    // Sort ascending. The majority element — appearing > n/2 times —
    // is guaranteed to be at the middle index after sorting.
    nums.sort((a, b) => a - b);
    return nums[Math.floor(nums.length / 2)];
}

Approach 4 — Boyer-Moore Voting O(n) / O(1) — Optimal

One pass, two variables. The majority element is the last candidate standing.

Python

from typing import List

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        # candidate: the current "survivor" after cancellations
        # count: net votes in favor of the candidate
        candidate = None
        count = 0

        for num in nums:
            if count == 0:
                # Previous candidate was fully cancelled (or we haven't started).
                # Adopt this element as the new candidate with 1 vote.
                candidate = num
                count = 1
            elif num == candidate:
                # This vote reinforces the current candidate.
                count += 1
            else:
                # This vote cancels one candidate vote.
                # A pair of (candidate, num) is eliminated from the "election".
                count -= 1

        # The majority element (> n/2 occurrences) can never be fully cancelled.
        # The problem guarantees one exists, so candidate is correct.
        return candidate

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
function majorityElement(nums) {
    // candidate: current survivor in the cancellation simulation
    // count: net reinforcements for the current candidate
    let candidate = null;
    let count = 0;

    for (const num of nums) {
        if (count === 0) {
            // No current candidate — adopt this element and cast the first vote
            candidate = num;
            count = 1;
        } else if (num === candidate) {
            // Same as candidate — reinforce it
            count++;
        } else {
            // Different from candidate — cancel one candidate vote
            count--;
        }
    }

    // The majority element outlasts all cancellations — it is the final survivor
    return candidate;
}

Complexity Analysis

Approach 1 — Brute Force

Approach 2 — HashMap

Approach 3 — Sort

*Technically O(log n) for the sort call stack, but typically described as O(1) extra space.

Approach 4 — Boyer-Moore (Optimal)

Boyer-Moore is the clear winner when both time and space are constrained. It is what interviewers expect you to arrive at for this problem.

Follow-up Questions

Majority Element II — LeetCode 229

Problem: Find all elements that appear more than ⌊n/3⌋ times.

The key question: Why does this version need two candidates instead of one?

Because of a simple counting argument: at most two elements can each appear more than n/3 times. If three elements each appeared more than n/3 times, their combined count would exceed n — which is impossible. So the answer set contains 0, 1, or 2 elements, and we need a candidate slot for each.

The extended Boyer-Moore for this problem maintains candidate1, count1, candidate2, count2. The logic is:

1. If current equals candidate1, increment count1.
2. Else if current equals candidate2, increment count2.
3. Else if count1 is zero, adopt current as candidate1 (count1 = 1).
4. Else if count2 is zero, adopt current as candidate2 (count2 = 1).
5. Otherwise, decrement both count1 and count2 (a triplet of distinct elements cancels).

Important: Unlike LC 169, the problem does not guarantee that elements exceeding n/3 exist. After the first pass, you must verify both candidates with a second pass counting their actual occurrences. Only return candidates whose actual count exceeds n/3.

The pattern generalizes: to find all elements appearing more than n/k times, maintain k-1 candidate slots.

Streaming Input

If the array arrives as a stream (you cannot store it), Boyer-Moore is the perfect algorithm — it processes elements one at a time and uses O(1) space. This is precisely why it is classified as a streaming algorithm, and why it was worth developing in 1981 even when the naive approaches worked for in-memory data.

If you need to handle the streaming case with no majority guarantee, you would need Boyer-Moore plus a separate frequency count (which requires knowing the total stream length ahead of time), or a different statistical approach.

This Pattern Solves

The cancellation voting pattern directly applies to:

• LeetCode 229 — Majority Element II: extend to two candidates for n/3 threshold
• LeetCode 1150 — Check if a Number Is Majority Element in a Sorted Array: binary search variant, same conceptual guarantee
• Streaming mode detection: real-time identification of dominant signals in data streams
• Distributed voting systems: any problem where you need to find a consensus value with bounded memory per node

More broadly, the idea that you can solve a problem by intelligently discarding information (rather than accumulating it) applies to algorithms like reservoir sampling, approximate frequency counting (Count-Min Sketch), and heavy hitter detection in network traffic analysis.

Key Takeaway

The Boyer-Moore Voting Algorithm is proof that a linear-time, constant-space solution can emerge from a problem that looks like it requires a frequency table. The trick is not to count everything — it is to recognize that the majority element, by virtue of its mathematical dominance, is the only element that cannot be cancelled to zero by the opposition. In your interview, present all four approaches, implement Boyer-Moore, and articulate the proof in one sentence: "The majority appears more than half the time, so even if it cancels one-for-one with every other element, those others run out first." That clarity is what separates candidates.