Majority Element — Boyer-Moore Voting

The Problem

You are given an array nums of length n, and you are told that one element appears more than n/2 times. Return that element. The follow-up is the classic constraint: O(n) time and O(1) extra space.

The key phrase is strictly more than half. That gap is what makes Boyer-Moore work; if the majority were only n/2 it would not.

Intuition

A hash map of counts solves it in O(n) time but O(n) space. Sorting and returning index n/2 works at O(n log n). Both are acceptable, neither is elegant.

The Boyer-Moore majority vote runs in O(n) time and O(1) space. Imagine each element pairing off with a different element and both canceling. Since the majority outnumbers every other value combined, at least one majority element survives the cancellation. The voting algorithm simulates that pairing in a single pass without ever materializing the pairs.

Maintain a candidate and a count. For each element: if count == 0, adopt the current element as the new candidate; else if the element equals the candidate, increment count; otherwise decrement count.

Explanation with Example

Take nums = [2, 2, 1, 1, 1, 2, 2]. The majority is 2 because it appears 4 times in an array of 7.

x:        2  2  1  1  1  2  2
cand:     2  2  2  2  1  1  1?
count:    1  2  1  0  1  0  1
                     ^         ^
            flip to 1     flip to 2
final candidate -> 2

The count went down, flipped candidate, went down again, flipped back, and ended on 2. Notice that the algorithm is allowed to temporarily believe wrong things during the sweep; the invariant only holds at the end.

Code

def majorityElement(nums):
    candidate = None
    count = 0
    for x in nums:
        if count == 0:
            candidate = x
        count += 1 if x == candidate else -1
    return candidate

class Solution {
    public int majorityElement(int[] nums) {
        Integer candidate = null;
        int count = 0;
        for (int x : nums) {
            if (count == 0) candidate = x;
            count += (x == candidate) ? 1 : -1;
        }
        return candidate;
    }
}

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = 0, count = 0;
        for (int x : nums) {
            if (count == 0) candidate = x;
            count += (x == candidate) ? 1 : -1;
        }
        return candidate;
    }
};

If majority is not guaranteed by the problem, a second pass should verify the candidate actually appears more than n/2 times.

Edge Cases

An array of length 1 returns its only element. An array where the majority is exactly n/2 + 1 (the minimum strict majority) still works because the gap of one is enough. If the problem did not guarantee a majority, you would have to do a second verification pass — the candidate from Boyer-Moore is only meaningful when a strict majority exists.

There is no concern about negative or large integers since the algorithm only compares for equality.

Complexity Analysis

Time is O(n): one pass, constant work per element. Space is O(1): just the candidate and count.

Compared to the hash-map solution it saves O(n) space, and compared to sorting it saves a logarithmic factor of time.

How to Explain It in an Interview

Open with the intuition: imagine pairing off elements that cancel each other. Since the majority outnumbers the rest combined, at least one majority element survives. Then write the code and trace through [3, 3, 4]. Mention the verification pass for the unguaranteed case, and note the generalization to “more than n/3 times” with two candidates and two counters.

Related Problems

• Majority Element II — Boyer-Moore with two candidates.
• Check If a Number Is Majority Element in a Sorted Array — uses binary search.
• Element Appearing More Than 25% — Boyer-Moore generalized.