Patterns this teaches:Hashing and Frequency MapsHeap and Top K
Top K Frequent Elements
A medium Heap interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Heap
- Sheets
- 3
- Core for
- 10 roles
The problem
Count how often each value appears in the array and return the k values that appear most often. The order of the returned values does not matter.
Example 1
- Input
- nums = [4,4,4,4,7,7,2], k = 2
- Output
- [4, 7]
- Why
- 4 appears four times and 7 twice; 2 appears once and is dropped.
Example 2
- Input
- nums = [1], k = 1
- Output
- [1]
- Why
- Only one element exists, so it is the single most frequent element.
Constraints
- 1 <= nums.length <= 10^5
- k is in the range [1, the number of unique elements in the array]
- -10^4 <= nums[i] <= 10^4
How to think about it
Updated 2026-09-29Frequencies are integers bounded between 1 and n. Once counts are tallied in a hash map, you do not need a general comparison sort on frequencies: you can either maintain a tiny min-heap of the top k frequencies or treat frequencies as indices into an array of buckets.
Approaches, worst first
Hash map with full sort
time O(u log u) · space O(u)
Count frequencies into a hash map, convert entries to an array, and sort by frequency descending. Take the first k keys. Correct and straightforward, but sorts all unique entries instead of isolating the top k.
Min-heap of size k
time O(u log k) · space O(u)
Stream map entries into a min-heap ordered by frequency, evicting the root whenever size exceeds k. The heap finishes containing the k highest frequency numbers.
Bucket sort by frequencyWrite this one
time O(n) · space O(n)
Create an array of lists where index f holds all elements that appear exactly f times. Scan the buckets backwards from index n down to 1, collecting elements until k values are gathered.
Where people lose marks · 3
- Sizing the frequency buckets to the maximum value in nums instead of nums.length. Values can be negative or large, but count can never exceed the total number of elements.
- Using a max-heap of all unique elements: building it takes O(u) but extracting k elements costs O(k log u), which degrades to O(u log u) when k approaches u. A min-heap capped at k stays bounded.
- Overlooking the k == unique elements edge case, where every single distinct number must be included in the result without missing trailing frequency ties.
The theory behind it
Heap — the ground this problem stands on. All Heap problems
What Heap is
A heap is a specialized tree that keeps only the single most extreme item at the very top. In a min-heap, every parent node is smaller than its children, so the smallest element in the entire collection sits immediately at the root. Unlike a binary search tree, a heap does not keep all items in full sorted order. It maintains only a partial order, making it fast at giving you the single smallest or largest item without spending time sorting everything else.
When to reach for it
Reach for a heap when a problem asks for the top k largest elements, the kth smallest value, or a running median from a stream of numbers. Signals include phrases like continuously finding the cheapest item, merging k sorted linked lists, or scheduling tasks with priorities. Whenever you need repeated access to the minimum or maximum value while items are added and removed dynamically, a priority heap is the tool.
How the pattern works
To find the k largest elements, keep a min-heap of fixed size k. Push incoming numbers into the heap; whenever the heap size grows past k, pop the top item, which is the smallest among them. After processing all elements, only the k largest remain. For a running median, balance two heaps: a max-heap holding the smaller half of numbers and a min-heap holding the larger half. In code, heaps are stored compactly as flat arrays where a node at index i has children at indices 2i plus 1 and 2i plus 2.
More Heap problems
Target Roles
Core requirement for 10 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .