Back to solutions

Majority Element

EasyArrays

Find the value that appears more than half the time.

Open problem
Constraints
  • 1 <= n <= 5 * 10^4
  • A majority element (count > n/2) is guaranteed to exist

Boyer-Moore voting

Time O(n)Space O(1)

Maintain a candidate and a counter. Each element votes: if it matches the candidate the counter goes up, otherwise it goes down. When the counter hits zero the next element becomes the new candidate. Because the majority appears more than n/2 times, it survives all the cancellations and remains as the final candidate.

Key terms
majority element:
A value that occurs strictly more than half of the time, so its count exceeds n/2.
candidate:
The current guess for the majority value while scanning.
Boyer-Moore voting:
An O(1)-space technique that pairs off and cancels different elements; only the majority can outlast all cancellations.
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;
}
Step by step
  1. Start with count = 0 and no fixed candidate.
  2. For each value x: if count is 0, adopt x as the candidate.
  3. If x equals the candidate, increment count; otherwise decrement it (a vote against).
  4. Different values cancel in pairs, so non-majority elements eliminate each other.
  5. Since the majority occurs more than n/2 times it cannot be fully cancelled, so the final candidate is the answer.