visual walkthrough
Top K Frequent Elements
Beats the O(n log n) sort with bucket sort; a favourite follow-up.
The idea
The count of any number is at most n, so counts can be used directly as array positions. Put each number into the bucket matching its count, then read the buckets from the highest count downwards until you have k numbers.
It skips sorting entirely, which is what makes it linear.
Complexity
| approach | time | space |
|---|---|---|
| Sort by count | O(n log n) | O(n) |
| Bucket by count | O(n) | O(n) |