LeetCode 347 Top K Frequent Elements - Solution

Count frequencies first. That's $O(n)$ with a hash map.

Now you need the top k by frequency. Bucket sort works because frequency values are bounded. The maximum frequency is $n$ (if one element appears in every position).

Create an array of buckets where bucket[freq] holds all elements with that frequency. With counts {1: 3, 2: 2, 3: 1}, bucket 3 contains [1], bucket 2 contains [2], bucket 1 contains [3].

Iterate from the highest bucket downward, collecting elements until you have k. The highest frequencies come first, so you naturally get the most frequent elements.