Return the k most frequent elements in an array.
Count frequencies with a hash map, then use a min-heap of size k to track the top k elements in O(n log k) time. An alternative bucket-sort approach achieves O(n) by indexing buckets by frequency.
How to think about it
Recognise the pattern
“Top k by some score” is a classic heap problem. You want the k largest frequencies without sorting everything. A min-heap of size k lets you evict the least-frequent candidate as you scan — keeping exactly the k best at all times.
A second signal: frequencies are bounded by n (the array length), which opens a bucket sort shortcut to O(n).
Build the approach step by step
Brute force: count all frequencies, sort by frequency descending, return the first k. Time O(n log n) — fine for small n, but the interviewer usually wants better.
Heap approach (O(n log k)):
- Build a frequency map in O(n).
- Maintain a min-heap of
(freq, element)pairs, capped at size k. - If the heap grows past k, pop the minimum — the globally least-frequent element falls off.
- Whatever remains in the heap is the answer.
Why a min-heap? Because you want to eject the smallest frequency to keep the largest k.
Bucket sort approach (O(n)):
- Create
n+1buckets wherebucket[f]holds all elements with exactlyfoccurrences. - Walk buckets from high to low, collect until you have k elements.
Complexity
| Approach | Time | Space |
|---|---|---|
| Sort all | O(n log n) | O(n) |
| Min-heap | O(n log k) | O(n + k) |
| Bucket sort | O(n) | O(n) |
The bucket sort is optimal but only works when frequencies are integers bounded by n — which they always are for array inputs. The heap approach generalises to streaming data.