Top K Frequent Elements
Top K Frequent Elements: return the k most frequent values in the array.
- 1 <= nums.length <= 10⁵
- -10⁴ <= nums[i] <= 10⁴
- k is in the range [1, the number of unique elements in the array].
- It is guaranteed that the answer is unique.
Intuition
The top k frequent elements problem has two distinct phases, and separating them makes it much easier to reason about: first count how often each value appears, then select the k largest counts. Counting is a single hash-map pass. What matters is that after counting, you are no longer working with n elements — you are working with the distinct values, which is often a far smaller set, and every selection strategy operates on that. Sorting the distinct values by frequency and taking the first k works, at O(d log d) for d distinct values. But you do not need a full ordering; you only need the top k, and two better options exploit that. A size-k min-heap keeps exactly the k most frequent values seen so far. Its root is the weakest of them, so a new candidate is compared against the root and either discarded or swapped in. That gives O(d log k), which is the standard answer. The bucket sort version is faster still and worth knowing, because it uses a bound specific to this problem: - No value can appear more than n times, so frequency itself is a small integer that can index an array. Create buckets indexed by frequency, drop each value into the bucket matching its count, then read buckets from the highest index downward until you have k values. No comparisons and no heap — O(n) overall, which beats any comparison-based approach.
Two independent steps hide in this one line: counting, then selecting. Counting is a hash map; selecting the top k from n counts is the heap question again. Recognising that "top k" never requires a full sort is the reusable part — you only need the k best, and a heap delivers that in O(n log k).
Approach
Before reading on: price up what counting everything costs here, then ask why only the extreme element matters and the rest need no ordering. Aim for O(n log k) time and O(n) space.
Count frequencies in one pass
Build a hash map from value to occurrence count by walking the array once. This is O(n) and reduces the problem from n elements to d distinct values, which is what every subsequent step operates on.
Select with a size-k min-heap
Push (frequency, value) pairs onto a heap and pop whenever the size exceeds k. The root is always the smallest frequency among the current top k, so it acts as the gate — anything less frequent is rejected immediately. Same pattern as Kth Largest Element in a Stream.
Understand why a min-heap tracks the largest
Keeping the smallest of the top k on top is what makes the comparison cheap: one look at the root decides whether a candidate belongs. A max-heap would put the wrong end within reach and force a scan to find the weakest member.
Or bucket by frequency for linear time
Create n + 1 buckets indexed by count and place each value into bucket[frequency]. Then walk the buckets from index n downward, collecting values until you have k. Frequencies are bounded by n, which is what makes this array indexing legal.
Choose based on the constraints
The heap is O(n + d log k) and is the expected interview answer. Bucketing is O(n) and strictly better asymptotically, at the cost of O(n) buckets even when only a few distinct values exist. Mentioning both, and the reason bucketing is possible here, is what separates a good answer from a complete one.
Solution & live demo
Common pitfalls
Sorting the whole frequency map
return [v for v, _ in freq.most_common()[:k]]
return [v for _, v in heapq.nlargest(k, ((f, v) for v, f in freq.items()))]
Fully ordering every distinct value is O(m log m) to answer a question about only k of them. nlargest keeps a heap of size k, so it's O(m log k) — and when k is small, that's the difference the interviewer is asking about.
Heapifying on the value rather than the frequency
heapq.nlargest(k, freq.items())
heapq.nlargest(k, ((f, v) for v, f in freq.items()))
freq.items() yields (value, frequency), so comparisons run on the value and you get the k largest numbers rather than the k most common. The sort key has to sit first in the tuple, which is why the pair is flipped.
Assuming ties break in a particular order
# expecting [1, 2] specifically when both appear twice
# any order among equally-frequent values is accepted
When several values share a frequency the problem accepts any of them, and the heap's internal ordering decides arbitrarily. Writing a test that pins one exact permutation makes a correct solution look broken.
Edge cases
Every value is returned; order among them is free.
Problem guarantees a unique answer set — ties never straddle the cut.