Back to solutions

Majority Element II

MediumArrays

Find all elements appearing more than n/3 times.

Open problem
Constraints
  • 1 <= n <= 5*10^4
  • -10^9 <= nums[i] <= 10^9

Boyer-Moore with two candidates

Time O(n)Space O(1)

At most two values can exceed n/3. Track two candidates with two counters. Each element either matches a candidate (increment its counter), seeds an empty candidate, or cancels one from each counter. A second pass verifies the surviving candidates actually exceed n/3.

Key terms
Boyer-Moore voting:
A counting/cancelling technique that finds frequent elements in O(1) space.
verification pass:
A second scan to confirm each candidate truly meets the frequency threshold.
// pass 1: find up to two candidates with Boyer-Moore
// pass 2: count occurrences and keep those > n/3
if (c1 > n / 3) res.push_back((int)cand1);
if (c2 > n / 3) res.push_back((int)cand2);
Step by step
  1. Maintain two (candidate, count) pairs. For each value, increment if it matches a candidate.
  2. Otherwise, if a counter is zero adopt the value as that candidate; else decrement both counters.
  3. After the pass, count true occurrences of each candidate.
  4. Output those whose count exceeds n/3, sorted.