Finding the majority element seems easy…
Just count frequencies, right?
But that takes extra space.
What if you could solve it in:
- O(n) time
- O(1) space
That’s where Moore’s Voting Algorithm shines.
Core Idea
The algorithm works like cancelling votes.
- Different elements cancel each other
- Majority element survives
Phase 1: Candidate Selection
int candidate = 0, count = 0;
for (int num : nums) {
if (count == 0) {
candidate = num;
count = 1;
} else if (num == candidate) {
count++;
} else {
count--;
}
}
Think of it as:
- Same element → increase count
- Different element → cancel
Phase 2: Verification
count = 0;
for (int num : nums) {
if (num == candidate) count++;
}
if (count > nums.length / 2) return candidate;
return -1;
- Ensures candidate is actually majority
Example
Array:
[3, 3, 4, 2, 3, 3, 3]
- Majority element = 3
The Real Insight
Majority element can’t be fully cancelled
Because it appears more than half the time.
Key Insights
- Uses vote cancellation logic
- Requires two passes
- No extra space needed
for more: https://www.quipoin.com/tutorial/data-structure-with-java/moore-voting-algorithm
