Top-K / Heap — Top K Frequent Elements
↗ LeetCode: Top K Frequent Elements · Medium · pattern chapter →
Given nums and integer k, return the k most frequent elements (any order).
Example 1 — nums=[1,1,1,2,2,3], k=2 → [1,2]Example 2 — nums=[1], k=1 → [1]
Constraints — 1 ≤ n ≤ 10⁵; 1 ≤ k ≤ #distinct. Brute sorts all n values by frequency in O(n log n) = 10⁵·17 ≈ 2·10⁶ ops. Heap of size k is O(n log k) — at k=10 that's 10⁵·4 = 4·10⁵ ops. Quickselect on frequency buckets is expected O(n) = 10⁵ ops.
Interview timer00:00
Approach 1 — Sort by frequency
Intuition. Count frequencies. Sort entries by frequency desc. Take the top k.
int[] topKFrequentSort(int[] nums, int k) {
Map<Integer, Integer> freq = new HashMap<>();
for (int x : nums) freq.merge(x, 1, Integer::sum);
List<int[]> pairs = new ArrayList<>();
for (var e : freq.entrySet()) pairs.add(new int[]{e.getKey(), e.getValue()});
pairs.sort((a, b) -> b[1] - a[1]);
int[] out = new int[k];
for (int i = 0; i < k; i++) out[i] = pairs.get(i)[0];
return out;
}Complexity — Time O(n + m log m) where m = distinct count; Space O(m).
Approach 2 — Min-heap of size k
Insight from sort. We don't need all m elements sorted; just the top k. A min-heap of size k evicts the smallest each insert; the root is the k-th largest frequency at the end.
Trap. Wrong polarity — a max-heap of all m needs O(m log m). Min-heap of size k does O(m log k).
int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> freq = new HashMap<>();
for (int x : nums) freq.merge(x, 1, Integer::sum);
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[1] - b[1]);
for (var e : freq.entrySet()) {
heap.offer(new int[]{e.getKey(), e.getValue()});
if (heap.size() > k) heap.poll();
}
int[] out = new int[k];
for (int i = k - 1; i >= 0; i--) out[i] = heap.poll()[0];
return out;
}Complexity — Time O(n + m log k); Space O(m + k). Great when k << m.
Approach 3 — Bucket sort by frequency
Insight from heap. Frequencies are bounded by n. Instead of sorting, put each element into a bucket indexed by its frequency; walk buckets from high to low.
int[] topKFrequentBucket(int[] nums, int k) {
Map<Integer, Integer> freq = new HashMap<>();
for (int x : nums) freq.merge(x, 1, Integer::sum);
List<Integer>[] buckets = new List[nums.length + 1];
for (var e : freq.entrySet()) {
int f = e.getValue();
if (buckets[f] == null) buckets[f] = new ArrayList<>();
buckets[f].add(e.getKey());
}
int[] out = new int[k];
int i = 0;
for (int f = buckets.length - 1; f >= 1 && i < k; f--)
if (buckets[f] != null) for (int x : buckets[f]) { out[i++] = x; if (i == k) break; }
return out;
}Complexity — Time O(n); Space O(n). Optimal.
Try it yourself
Complexity summary
| Approach | Time | Space |
|---|---|---|
| Sort by freq | O(n + m log m) | O(m) |
| Min-heap of size k | O(n + m log k) | O(m + k) |
| Bucket sort | O(n) | O(n) |
When to use which
- k tiny compared to m → heap is idiomatic and easy to defend.
- Interviewer probes "beat log k" → bucket sort. Trades a bit of space for O(n).
Related problems (same ladder applies)
- K Closest Points to Origin — same shape with distance instead of freq
- Kth Largest Element in a Stream — min-heap of size k over a stream
- Kth Smallest Element in a Sorted Matrix — heap on rows
- Reorganize String — max-heap on char frequencies