Why it works
- The heap is the card’s k largest with another key: it compares how often numbers appear, not the numbers themselves. So 9, the largest number, is popped, because it is the rarest.
- Each distinct number goes through the heap once, and whenever there are k + 1 the rarest of them leaves. So the k most frequent stay to the end.
- The heap holds at most k + 1 numbers, so with many distinct numbers it is cheaper than sorting all of them by count.
Complexity
Time O(n + m log k): one pass to count n numbers, then m distinct numbers through a heap of at most k + 1. Memory O(m) for the counts.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗