visual walkthrough
Majority Element
Introduces an O(1)-space voting trick that surprises most candidates.
The idea
If one value appears more than half the time, it can outvote every other value combined. Pair each vote for it with a vote against it: whatever is left standing must be the majority.
Boyer–Moore does exactly that with a single candidate and a counter, no map needed.
Complexity
| approach | time | space |
|---|---|---|
| Count with a map | O(n) | O(n) |
| Boyer–Moore voting | O(n) | O(1) |