Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Count every value with a hash map, then select the k most frequent. The interview-grade answer is a min-heap of size k keyed by frequency: push (count, value) and pop whenever the heap exceeds k, leaving the k largest — O(n log k) time. The strongest answer is bucket sort: index values by their frequency (1..n) and read from the high-frequency end, giving true O(n) time.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you separate 'count' from 'select', and whether you reach for a size-k heap instead of fully sorting — plus whether you know the O(n) bucket-sort upgrade.
Where candidates slip
Building a max-heap of all n elements (O(n log n)) instead of a min-heap capped at size k (O(n log k)), or sorting the whole frequency map when only the top k matter.
How to stand out
Name three tiers out loud — sort O(n log n), size-k heap O(n log k), bucket sort O(n) — then justify which to pick from k versus n, and mention quickselect as the O(n)-average comparison-based alternative.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewFind the k most frequent valuesNeed strict O(n)?YesNoExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Min-Heap of Size K
1Hint 1Explore hintHide hint
Two phases: first tally counts, then pick the top k. What structure gives O(1) counting? And what structure efficiently maintains 'the best k seen so far'?
2Hint 2Explore hintHide hint
Build a hash map value → count in O(n). Now you have at most n distinct (value, count) pairs to rank.
3Hint 3Explore hintHide hint
Push each (count, value) into a min-heap. After every push, if the heap holds more than k items, pop the smallest. The smallest is always the least frequent survivor, so the k most frequent remain.
A · Core idea
Solve it in two clean phases.
Phase 1 — count. Walk nums once building a hash map from value to its frequency. This is O(n) and reduces the problem to ranking at most n distinct (value, count) pairs.
Phase 2 — keep only the k best with a min-heap. A min-heap (smallest on top) is the counter-intuitive but correct choice. Push (count, value) for each distinct value. The instant the heap grows past k, pop the top — which is the least frequent element currently held. Because we only ever discard the smallest, whatever remains after processing every value is exactly the k largest by frequency.
Why min-heap, not max-heap. It feels natural to build a max-heap of all n elements and pop k times — but that's O(n + k log n) with an O(n) heapify, and more importantly stores all n elements. The size-k min-heap caps memory at k and makes each operation O(log k) instead of O(log n). When k ≪ n this is a real win and signals you understand 'top-K' as a bounded-heap pattern, not a sort.
Why (count, value) ordering matters. The heap must order by frequency, so frequency is the first tuple element (Python compares tuples lexicographically; Java needs a comparator on count). Getting the comparator backwards is the classic bug — you'd keep the k least frequent.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
nums = [1, 1, 1, 2, 2, 3], k = 2Hash-map state
after counting
Match found
value → frequency
[2, 1]C · Code with teaching comments
Reference implementation previewpublic int[] topKFrequent(int[] nums, int k) { Map<Integer, Integer> count = new HashMap<>(); for (int n : nums) { count.merge(n, 1, Integer::sum); }Explore the full codeHide the full code
D · Why it works and complexityO(n log k) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
A min-heap of size k is a sliding 'hall of fame': the doorman (the heap top) is always the weakest current member, so admitting a stronger candidate evicts exactly the right one. You never need to see all n elements at once — perfect for streams where n is unbounded but k is fixed.
ComplexityO(n log k) time, O(n) space — Counting is O(n). Each of the ≤ n distinct values triggers a push and possibly a pop, each O(log k) because the heap never exceeds size k. Total O(n log k). The map plus heap are O(n) space.
E · Edge cases and pitfalls6nums = [1], k = 1 — Map {1:1}; push (1,1); heap size 1 ≤ 1; return [1].Explore edge casesHide edge cases
Edge cases handled
nums = [1], k = 1Map {1:1}; push (1,1); heap size 1 ≤ 1; return [1].nums = [3,0,1,0], k = 1Map {3:1,0:2,1:1}; only 0 (freq 2) survives the size-1 heap; return [0]. Tests 0 as a value.all distinct, k = nEvery value has freq 1; the heap keeps all n; returns every value.
Pitfalls
- Using a max-heap of all n elements — O(n log n) and O(n) heap memory instead of O(n log k) and O(k).
- Reversing the comparator so it becomes a max-heap of size k — you'd return the k LEAST frequent.
- Popping only when size > k+1 (off-by-one) — leaves k+1 elements in the heap.
Approach 2 of 2 · Optimal
Bucket Sort by Frequency (Optimal O(n))
1Hint 1Explore hintHide hint
A frequency can never exceed n (you only have n elements). What if you indexed values by their frequency directly?
2Hint 2Explore hintHide hint
Make an array of n+1 buckets. Place each value into bucket[its frequency]. Now bucket[f] lists every value occurring exactly f times.
3Hint 3Explore hintHide hint
Walk the buckets from the highest frequency downward, collecting values until you have k. No comparisons, no log factor — pure O(n).
A · Core idea
Exploit a hard bound: with n elements, no value can appear more than n times. So frequencies live in the small integer range [1, n] and can be used as array indices.
Build the buckets. Create buckets[0..n], where buckets[f] is a list of all values whose frequency is exactly f. After counting, iterate the map once and append each value to its frequency's bucket. This is a counting-sort idea: instead of comparing frequencies, we place values at their frequency.
Read from the top. Walk f from n down to 1. Each bucket you hit contains the next-most-frequent group of values; append them to the result until you've collected k. Because higher indices are scanned first, the most frequent come out first.
Why this beats the heap. There's no comparison and no logarithm anywhere — every step is a direct index or append. The total work is linear in n, which is the theoretical floor (you must at least read the input). This is the answer the follow-up is fishing for.
Why n+1 buckets. Frequencies range from 1 to n inclusive, so we need indices up to n. Allocating index 0 (always empty) keeps the indexing arithmetic trivial — buckets[f] with no offset.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
nums = [1, 1, 1, 2, 2, 3], k = 2Interactive diagram
Bucket layout for the example
fill bucketsValues placed at the index equal to their frequency; we read right-to-left.
[1, 2]C · Code with teaching comments
D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
Bucket sort works here purely because the key we sort on (frequency) is bounded by n. The instant the thing you're ranking has a small bounded range, a comparison sort is overkill — counting/bucket placement turns O(n log n) into O(n). Spotting that bound is the whole trick.
ComplexityO(n) time, O(n) space — Counting is O(n). Filling buckets visits each distinct value once — O(n). Scanning buckets high-to-low touches each bucket index and each stored value once — O(n) total. Buckets plus map are O(n) space.
E · Edge cases and pitfalls6nums = [1,2,3,4], k = 2 — All freq 1 → buckets[1]=[1,2,3,4]; we take the first two scanned. Any two are valid (problem guarantees uniqueness in real inputs).Explore edge casesHide edge cases
Edge cases handled
nums = [1,2,3,4], k = 2All freq 1 → buckets[1]=[1,2,3,4]; we take the first two scanned. Any two are valid (problem guarantees uniqueness in real inputs).nums = [7,7,7,7], k = 1buckets[4]=[7]; scan from f=4 → return [7].k equals number of distinct valuesScan collects every value across all non-empty buckets.
Pitfalls
- Sizing buckets to max(value) instead of n — wrong axis; you bucket by FREQUENCY, which is bounded by n.
- In Python, `[[]] * (n+1)` creates n+1 references to ONE list — use a comprehension so each bucket is independent.
- Forgetting to stop at k — you'd over-collect when a bucket holds several values.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int[] topKFrequent(int[] nums, int k) { Map<Integer, Integer> count = new HashMap<>(); for (int n : nums) { count.merge(n, 1, Integer::sum); }Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Max-heap of n elements instead of size-k min-heap
Heaping all distinct values and popping k times is O(n log n)-ish and stores everything. A size-k min-heap caps memory at k and each op at log k.
Explore the code comparisonHide the code comparison
Max-heap of n elements instead of size-k min-heap
Heaping all distinct values and popping k times is O(n log n)-ish and stores everything. A size-k min-heap caps memory at k and each op at log k.
Don't write this
heap = [(-f, v) for v, f in count.items()] # all n, max-heap
heapq.heapify(heap)
return [heapq.heappop(heap)[1] for _ in range(k)]Write this instead
heap = []
for v, f in count.items():
heapq.heappush(heap, (f, v))
if len(heap) > k:
heapq.heappop(heap)
return [v for f, v in heap]2Reversed comparator keeps the wrong k
If the size-k heap is ordered as a MAX-heap on frequency, every pop removes the most frequent, so you end up retaining the k LEAST frequent values.
Explore the code comparisonHide the code comparison
Reversed comparator keeps the wrong k
If the size-k heap is ordered as a MAX-heap on frequency, every pop removes the most frequent, so you end up retaining the k LEAST frequent values.
Don't write this
PriorityQueue<int[]> heap =
new PriorityQueue<>((a, b) -> b[1] - a[1]); // max-heap
heap.offer(new int[]{key, freq});
if (heap.size() > k) heap.poll(); // pops the MOST frequentWrite this instead
PriorityQueue<int[]> heap =
new PriorityQueue<>((a, b) -> a[1] - b[1]); // min-heap
heap.offer(new int[]{key, freq});
if (heap.size() > k) heap.poll(); // pops the LEAST frequent3Shared bucket references in Python
`[[]] * (n+1)` makes every index point to the SAME list, so appending to one bucket appears in all of them, corrupting the result.
Explore the code comparisonHide the code comparison
Shared bucket references in Python
`[[]] * (n+1)` makes every index point to the SAME list, so appending to one bucket appears in all of them, corrupting the result.
Don't write this
buckets = [[]] * (len(nums) + 1)
buckets[freq].append(value) # mutates every bucketWrite this instead
buckets = [[] for _ in range(len(nums) + 1)]
buckets[freq].append(value) # each bucket independentRevise
Carry the pattern into the interview
Pattern to remember
Frequency map + size-k heap (or bucket sort)
Code pattern to memorize
count = Counter(nums)
heap = [] # min-heap of (freq, val)
for val, f in count.items():
heappush(heap, (f, val))
if len(heap) > k: heappop(heap)
return [val for f, val in heap]Rules to remember
- 1Use a min-heap of size k, not a max-heap of size n — you only ever need to keep the k best.
- 2Pop when the heap exceeds k, so the smallest frequency falls out and the k largest survive.
- 3If the interviewer wants strict O(n), pivot to bucket sort — frequencies are bounded by n, so they index cleanly into n+1 buckets.
- 4k is guaranteed
1 ≤ k ≤ number of distinct elements, so the answer is always well-defined — no need to handle k > distinct. - 5Full sort of (value, count) pairs is O(n log n) — fine to mention, but the heap (O(n log k)) and bucket sort (O(n)) both beat it.
Use this pattern when
- 'Top K', 'K most frequent', 'K largest/smallest' over a collection
- You need a partial ordering of the K best, not a full sort
- Streaming data where K stays small relative to n
- Frequencies / keys are bounded integers (then bucket sort wins)
Choose another pattern when
- k ≈ n → just sort, the heap gives no advantage
- You need the elements fully sorted → sort directly
- Single max/min (k = 1) → a linear scan beats a heap
- Data fits a bounded range → counting / bucket sort is O(n)
Interview takeaway
Top-K is the signature heap problem: a size-k heap converts 'find the K best' from an O(n log n) sort into O(n log k). When the keys you rank are bounded (like frequencies ≤ n), bucket sort drops it to O(n). Same shape powers K Closest Points, K Largest, and Kth Largest in a Stream.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternTop-K via size-k heap (O(n log k)) or bucket sort (O(n)). Reach for it whenever you need the K best by some key without a full sort. Same family as Kth Largest Element, K Closest Points to Origin, and Sort Characters By Frequency.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Kth Largest Element in an ArrayComing soonSize-k min-heap of values (not frequencies), or quickselect for O(n) average.
- K Closest Points to OriginSame size-k heap, keyed by squared distance instead of frequency.
- Top K Frequent WordsComing soonAdd a tie-break: same frequency → lexicographically smaller first. Careful heap comparator.
- Sort Characters By FrequencyComing soonSame count + bucket-by-frequency idea, but emit characters repeated by their count.