Top K Frequent Elements
Problem
nums and an integer k.
Return the k values that occur most often in nums, in any
order. The input guarantees that the answer is unique.[1,1,1,2,2,3], k=2Output[1,2][1], k=1Output[1]1 ≤ n ≤ 105 · -104 ≤ nums[i] ≤ 104 · 1 ≤ k ≤ #distinct · Follow-up: beat O(n log n).
Try it yourself
class Solution {
public int[] topKFrequent(int[] nums, int k) {
}
}
freq and read buckets from high to low
— a counting sort that runs in linear time.Instinct "K largest / smallest / closest / most frequent", or "always take the best available next"? Keep a heap - size k for top-K, or a ready-queue for scheduling.
Memory hack Guard the top-K club with a bouncer - a min-heap of size k whose root is the weakest member; anyone stronger kicks them out.
Open the Heap & Top-K guide →Approaches
Brute ForceCount + Sort by Frequency
O(n log n)Space O(n)Count occurrences with a hash map, sort the distinct values by count
descending, and take the first k. Sorting all m ≤ n distinct values
does far more work than needed when k is small.
public int[] topKFrequent(int[] nums, int k) { Map<Integer, Integer> count = new HashMap<>(); for (int x : nums) count.merge(x, 1, Integer::sum); List<Integer> keys = new ArrayList<>(count.keySet()); keys.sort((a, b) -> count.get(b) - count.get(a)); int[] result = new int[k]; for (int i = 0; i < k; i++) result[i] = keys.get(i); return result; }
Simple and correct, but fails the follow-up (O(n log n)).
BetterCount + Min-Heap of Size k
O(n log k)Space O(n)Push distinct values into a min-heap ordered by count; whenever it exceeds
k, pop the least frequent. The survivors are the k most frequent.
Heap operations cost log k, not log n.
public int[] topKFrequent(int[] nums, int k) { Map<Integer, Integer> count = new HashMap<>(); for (int x : nums) count.merge(x, 1, Integer::sum); PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> count.get(a) - count.get(b)); for (int key : count.keySet()) { heap.offer(key); if (heap.size() > k) heap.poll(); // evict least frequent } int[] result = new int[k]; for (int i = k - 1; i >= 0; i--) result[i] = heap.poll(); return result; }
Beats sorting when k « n; still a log factor.
OptimalCount + Bucket Sort by Frequency
O(n)Space O(n)Create n + 1 buckets where bucket[f] lists values seen
exactly f times. Walk buckets from n down to 1, collecting
values until k are gathered. No comparisons, so no log factor.
public int[] topKFrequent(int[] nums, int k) { Map<Integer, Integer> count = new HashMap<>(); for (int x : nums) count.merge(x, 1, Integer::sum); List<Integer>[] bucket = new List[nums.length + 1]; for (Map.Entry<Integer, Integer> e : count.entrySet()) { int f = e.getValue(); if (bucket[f] == null) bucket[f] = new ArrayList<>(); bucket[f].add(e.getKey()); } int[] result = new int[k]; int idx = 0; for (int f = nums.length; f >= 1 && idx < k; f--) { if (bucket[f] == null) continue; for (int v : bucket[f]) { if (idx == k) break; result[idx++] = v; } } return result; }
Dry run[1,1,1,2,2,3], k=2 → buckets indexed by frequency 0..6
- build·321···cnt 1:3, 2:2, 3:1
- f=6..4·321·f··empty buckets
- f=3·321f···take 1 → [1]
- f=2·32f1···take 2 → [1,2] ✔
Linear time — answers the follow-up.
At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Count + Sort by Frequency | O(n log n) | O(n) |
| Better | Count + Min-Heap of Size k | O(n log k) | O(n) |
| Optimal | Count + Bucket Sort by Frequency | O(n) | O(n) |
- Bucket array of size n instead of n + 1 — a value seen n times overflows.
- Using a max-heap of all values — O(n log n) again; keep a size-k min-heap.
- Not stopping at exactly k inside a bucket holding several values.
- Clarify that order doesn't matter and the answer is unique.
- Walk sort → heap → buckets, stating each complexity.
- Point out frequencies are bounded by n — that's what enables counting sort.