Why it works
- Count each value as you go: the map holds value → how many times so far, and finds the count at once.
- The answer appears more than n / 2 times, and then no other value can: together they would not fit in the array. So the first count that goes over n / 2 is the answer.
- That is why the run may stop right there: the numbers after it cannot change the answer.
Complexity
Time O(n): at most one pass. Memory O(n): the map may hold many different values. Boyer–Moore voting finds the answer with O(1) memory, but it is a different idea.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗