#169
Majority Element
Easy Moore's voting
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
One value appears more than n/2 times. Return it, ideally in O(n) time and O(1) space.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: which value appears more than half the time?
Why this works: pair every majority vote against a different vote. The majority has more than half, so it always survives the cancelling.
Example: [2, 2, 1, 1, 1, 2, 2]
2 (c1), 2 (c2), 1 (c1), 1 (c0)1 → new candidate 1 (c1), 2 (c0)2 → new candidate 2 (c1) → answer 2
✦Hints open one at a time
Pair each majority vote against a different vote. Who survives?
Keep a candidate and a counter: same value +1, different value −1, counter 0 → new candidate.
↗Approach
Boyer–Moore voting. Because the majority has more than half the votes, it can't be cancelled out completely, so the final candidate is the answer (guaranteed to exist here).
</>Solution (Java)
class Solution {
public int majorityElement(int[] nums) {
int candidate = 0, count = 0;
for (int x : nums) {
if (count == 0) candidate = x; // start a new vote
count += (x == candidate) ? 1 : -1;
}
return candidate;
}
}!Common mistake
Sorting and taking the middle — correct, but O(n log n). Interviewers expect the voting trick.
Complexity
- Time: O(n).
- Space: O(1).
Topic: Kadane, Dutch Flag & Moore's Voting
🎬 Episodes 11–13: video coming soon