#229
Majority Element II
Medium Extended Moore's voting
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return every value that appears more than n/3 times.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: all values that appear more than n/3 times (at most two).
Why this works: keep two candidates; a third different value cancels one vote from each. Then count the two candidates to confirm.
Example: [3, 2, 3]
candidates 3 and 2 survivecounts: 3 → 2 times > 1 ✓, 2 → 1 time ✗answer [3]
✦Hints open one at a time
At most two values can appear more than n/3 times.
Keep two candidates and two counters; a third value decrements both.
Candidates aren't guaranteed — verify them with a second pass.
↗Approach
Voting with two slots. If x matches a candidate, increment its count; else if a count is 0, take that slot; else decrement both. Then count the two candidates for real and keep those above n/3.
</>Solution (Java)
import java.util.*;
class Solution {
public List<Integer> majorityElement(int[] nums) {
int c1 = 0, c2 = 1, n1 = 0, n2 = 0; // different starting candidates
for (int x : nums) {
if (x == c1) n1++;
else if (x == c2) n2++;
else if (n1 == 0) { c1 = x; n1 = 1; }
else if (n2 == 0) { c2 = x; n2 = 1; }
else { n1--; n2--; }
}
n1 = 0; n2 = 0;
for (int x : nums) {
if (x == c1) n1++;
else if (x == c2) n2++;
}
List<Integer> res = new ArrayList<>();
if (n1 > nums.length / 3) res.add(c1);
if (n2 > nums.length / 3) res.add(c2);
return res;
}
}!Common mistake
Skipping the verification pass; a candidate can survive voting without being a real majority.
Complexity
- Time: O(n).
- Space: O(1).
Topic: Kadane, Dutch Flag & Moore's Voting
🎬 Episodes 11–13: video coming soon