Majority Element II
Return every value that appears more than n/3 times, in linear time and constant space, with two-candidate Boyer-Moore voting and a second counting pass.
Problem Understanding
Majority Element II: given an integer array nums of size n, return all values that appear more than ⌊n/3⌋ times, in any order. The follow-up: O(n) time and O(1) space.
Examples: [3,2,3] → [3]; [1] → [1]; [1,2] → [1,2].
The Intuition: Cancel Three Different Values at a Time
This extends Majority Element, where one candidate cancels against one other value. With a threshold of n/3, at most two values can win, so keep two candidates.
- Match: a value equal to a candidate adds a vote to it.
- Empty slot: if a slot has count 0, the value takes it.
- Cancel: otherwise the value and one vote from each candidate are thrown away together, three different values at once.
- Count: the slots now hold every possible winner, plus maybe a decoy, so count both and keep those above n/3.
The plain hash map count works too, at O(n) space, like Top K Frequent Elements.
Interactive Walkthrough
TWO EMPTY SLOTS
nums
0
1
2
3
4
5
6
7
slot 1: empty
0 VOTES
slot 2: empty
0 VOTES
need >
2
copies
:
winners
:
Two empty candidate slots. A winner needs more than 8 / 3, so at most two can exist
Next
Slot 1 is empty (count 0): 1 becomes candidate 1
nums
The value being read is solid. Each slot's votes are drawn as tokens, so a cancel takes one token from both rows. In the counting pass, the copies of the candidate being checked are tinted. Try Decoy to see a survivor fail the count.
Dry Run Table
Input: [1,1,1,3,3,2,2,2], n = 8, so a winner needs more than 2 copies.
| x | What happens | slot 1 | slot 2 |
|---|---|---|---|
| 1 | slot 1 empty, take it | 1 ×1 | - |
| 1, 1 | match slot 1 | 1 ×3 | - |
| 3 | slot 2 empty, take it | 1 ×3 | 3 ×1 |
| 3 | match slot 2 | 1 ×3 | 3 ×2 |
| 2 | no match, cancel | 1 ×2 | 3 ×1 |
| 2 | no match, cancel | 1 ×1 | 3 ×0 |
| 2 | slot 2 at 0, take it | 1 ×1 | 2 ×1 |
Count: 1 appears 3 times, 2 appears 3 times, both more than 2. Answer: [1,2].
The Solution Template
One voting pass, one counting pass. Java, C++ and C start both slots at 0 with count 0; counting with else if keeps a candidate from being reported twice when both slots hold the same placeholder.
Majority Element II Code
1var majorityElement = function(nums) {2 let c1 = null, c2 = null, k1 = 0, k2 = 0;3 for (const x of nums) {4 if (x === c1) k1++;5 else if (x === c2) k2++;6 else if (k1 === 0) { c1 = x; k1 = 1; }7 else if (k2 === 0) { c2 = x; k2 = 1; }8 else { k1--; k2--; }9 }10 return [c1, c2].filter((c) => c !== null && nums.filter((x) => x === c).length > nums.length / 3);11};
Edge Cases & Common Mistakes
- Skipping the count: survivors are only candidates;
[3,2,3]leaves 2 in a slot. - Order of the checks: test both matches before taking an empty slot, or one value can end up in both slots.
- Threshold: strictly more than ⌊n/3⌋, so with n = 6 a value needs 3 copies.
- Small arrays: with n ≤ 2 every distinct value qualifies.
- No winner: the answer can be empty, e.g.
[1,2,3].
Summary
Keep two candidates with counts. Match adds a vote, an empty slot takes the value, anything else cancels one vote from both. Then count both candidates and keep those above n/3. O(n) time, O(1) space.
More practice: DSA interview questions with answers · patterns cheat sheet