Majority Element
An element appears more than ⌊n/2⌋ times. Return it. (It is guaranteed to exist.)
Intuition
The majority element outnumbers everything else combined. If we pair off each majority vote against one non-majority vote, the majority always has leftovers. Boyer-Moore voting exploits exactly this cancellation.
Approach
The easy answer, and why we can do better
Counting occurrences in a hash map and returning the one above n/2 works and is O(n) time — but it uses O(n) extra space. The problem has special structure we can exploit: one element appears more than all the others combined. That strict majority is a strong promise, and it lets us solve it with two integers instead of a whole map.
Pair off opposites until one survivor remains
Imagine repeatedly removing two elements with different values — each removal deletes one majority element and one non-majority element at most. Because majority elements strictly outnumber everyone else, they can never be fully cancelled; some must survive. Boyer-Moore voting implements this with a candidate and a count: a matching value votes +1, a different value votes −1, and these −1s are exactly the 'cancellations.'
Re-elect whenever the count hits zero
Walk once. Whenever count drops to 0, the cancellations have wiped out the current candidate, so adopt the current element as the new candidate. Then apply its vote. Even if early noise installs a wrong candidate, a strict majority guarantees it gets re-elected and ends with count > 0. The final candidate is the answer — O(n) time, O(1) space.
Solution & live demo
Edge cases
Even if early non-majority votes set a wrong candidate, the trailing majority resets and re-elects itself — the count cannot survive against a strict majority.
count starts 0, the element becomes the candidate, and is returned.
That is still a strict majority, so cancellations leave the candidate standing.