Top K Frequent Elements: Keep Only K Heap Candidates
Learn Top K Frequent Elements with a frequency map and size-k min-heap, including JavaScript code, walkthrough, complexity, and heap invariants.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Top K Frequent Elements has two separate jobs hidden in one sentence: count how often every value occurs, then retain only the best k counts. Mixing those jobs is where many implementations become unnecessarily expensive.
The visualizer uses a frequency map followed by a min-priority queue keyed by frequency. The heap is not asked to order every distinct value permanently. It only protects the current top k candidates, with the weakest of those candidates at the root.
The problem
Return the k most frequent values from an integer array. The values may be returned in any order.
Input: nums = [1, 1, 1, 2, 2, 3], k = 2
Output: [1, 2]The input is not sorted, so the first pass must establish the missing frequency information. After that, the answer depends on distinct values rather than raw array positions.
The brute force baseline
Count frequencies, put every distinct entry into an array, sort that array descending by frequency, then take the first k. If there are u distinct values, that costs O(n + u log u) time.
Sorting is a good baseline, but it orders entries that will never be returned. When k is much smaller than u, a bounded heap removes those losers as soon as they are known to be worse than the current candidates.
The key insight: the heap root is the disposable candidate
Use a map for value → frequency. Then push each map entry into a min-heap by frequency. Whenever its size exceeds k, remove the root.
That root is the least frequent item among the candidates currently kept. Evicting it preserves the invariant: after each distinct value is processed, the heap contains the best min(k, processedCount) entries seen so far. A max-heap would expose the winner, not the candidate that should be discarded.
The optimal solution
function topKFrequent(nums, k) {
const counts = new Map();
for (const num of nums) {
counts.set(num, (counts.get(num) ?? 0) + 1);
}
const heap = new MinPriorityQueue({ priority: entry => entry.freq });
for (const [val, freq] of counts) {
heap.enqueue({ val, freq });
if (heap.size() > k) heap.dequeue();
}
return heap.toArray().map(({ element }) => element.val);
}The visualizer's canonical code follows the same two phases: build map, push { val, freq } into a min-priority queue, pop after an overflow, then map the remaining entries back to values. Library method names vary, but the heap invariant does not.
Walkthrough
For [1, 1, 1, 2, 2, 3] and k = 2, the map is {1: 3, 2: 2, 3: 1}.
| Entry considered | Heap after push | Size action | Heap meaning |
|---|---|---|---|
{1, 3} | [{1, 3}] | Keep | Best one candidate |
{2, 2} | [{2, 2}, {1, 3}] | Keep | Best two candidates |
{3, 1} | [{3, 1}, {1, 3}, {2, 2}] | Pop {3, 1} | Best two remain |
The heap's internal array is not sorted. Only the root is guaranteed to be the minimum-frequency entry, which is all the algorithm needs.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Count then sort | O(n + u log u) | O(u) | Sorts all distinct values |
| Frequency map + size-k heap | O(n + u log k) | O(u + k) | Each distinct entry enters a bounded heap |
Here u is the number of distinct values. The frequency map is O(u); the heap never contains more than k entries.
Common mistakes
- Using a max-heap and removing its root on overflow, which discards the most frequent candidate.
- Pushing every occurrence into the heap instead of counting first.
- Assuming
heap.toArray()is frequency-sorted; the problem allows any result order. - Forgetting that ties are valid: multiple sets can be correct when frequencies match.
Where this pattern shows up next
- Min-Heap Operations explains the parent-child invariant behind heap updates.
The same size-k eviction idea appears in streaming and selection problems: retain only the best candidates seen so far, and make the root the one that can be safely replaced next.
Step through Top K Frequent Elements interactively to watch the root become the eviction target.
FAQ
Why use a min-heap for the most frequent elements?
The heap holds the winners, and its root should be the easiest winner to replace. A min-heap puts the smallest retained frequency at the root, so an overflow removes exactly the current weakest candidate.
What is the complexity when k equals the number of distinct values?
The heap can grow to u, so the heap phase becomes O(u log u), equivalent in asymptotic cost to sorting. The bounded-heap advantage is strongest when k is much smaller than the number of distinct values.
Do I need to sort the final answer?
No. The problem permits any order. The heap only guarantees its root relation, and returning the remaining values directly avoids work that does not affect correctness.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.