Top K Frequent Elements (LeetCode 347)
You're given an integer array nums and an integer k. Report the k values that appear most often in nums — ties in return order don't matter, so any ordering of the k values is accepted.
Follow-up: a full O(n log n) sort is accepted, but can you do better? Aim for a time complexity below O(n log n), where n is the length of nums.
Worked Examples
nums = [1,1,1,2,2,3], k = 2[1,2]1 appears 3 times and 2 twice, more often than 3.nums = [1], k = 1[1]nums = [1,2,1,2,1,2,3,1,3,2], k = 2[1,2]1 and 2 appear 4 times each; 3 appears only twice.⚖️Formal Constraints & Bounds
1 <= nums.length <= 105-104 <= nums[i] <= 104kis in the range[1, the number of unique elements in the array].It is guaranteed that the answer is unique.
Core Insight
Bounding the heap to size K ensures all push/pop heap operations take O(log K) rather than O(log N) time.
Real-World Scenario & Production Applications
Real-time analytics trending topics (Twitter/X hashtag rankings) and cache eviction telemetry.
Subproblems & Recurrence Decomposition3 Phases
Count element frequencies in O(N) time using a hash map count = Counter(nums).
count = Counter(nums)Step-by-Step Execution Trace Table
| Step | Item Pushed (freq, val) | Min-Heap State After Push | Size | Over k = 2? | Evicted Root | Heap State After Step |
|---|---|---|---|---|---|---|
| 1 | (3, 1) | [(3, 1)] | 1 | No | — | [(3, 1)] |
| 2 | (2, 2) | [(2, 2), (3, 1)] | 2 | No | — | [(2, 2), (3, 1)] |
| 3 | (1, 3) | [(1, 3), (3, 1), (2, 2)] | 3 | Yes | (1, 3) (lowest freq) | [(2, 2), (3, 1)] |
| 1 | counts = Counter(nums) |
| 2 | min_heap = [] |
| 3 | for value, count in counts.items(): |
| 4 | heappush(min_heap, (count, value)) |
| 5 | if len(min_heap) > k: |
| 6 | heappop(min_heap) |
| 7 | return [value for count, value in min_heap] |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Identifying the $K$ most frequent elements requires counting occurrences with a hash map and then extracting the $K$ highest frequencies. Maintaining a min-heap of capacity $K$ keyed by frequency ensures that the smallest frequency among the current top $K$ sits at the root. Evicting the root whenever size exceeds $K$ bounds runtime to $O(N \log K)$ and space to $O(N + K)$. 🏆 The Analogy: A Leaderboard With Only k Seats
Imagine a leaderboard with exactly k seats, currently occupied by whoever has qualified so far. A new contender only earns a seat by beating the weakest person currently on the board — and the moment they do, the weakest person gets bumped off. You never need to compare a new contender against everyone in the whole competition, only against the single weakest name currently on the board, which a min-heap hands you instantly.
🔑 The Key Idea in the Code
A min-heap (not a max-heap) is the right tool specifically because the operation you need repeatedly is "find and remove the smallest" — the weakest current qualifier — not the largest.
Sorting full dictionary : Sorting all unique elements by frequency is . A min-heap of size keyed on frequency maintains the top in , and bucket sort achieves .
Inverting heap key ordering: Storing
(key, freq)in Python's min-heap sorts primarily bykey. Always store(freq, key)so the heap prioritizes frequency.Popping from min-heap leaves root as smallest: In a min-heap of size , the elements left in the heap at the end are the most frequent, but popped in ascending order. Reverse if descending order is requested.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Find top / most frequent K elements from unsorted data.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Decision rule: push every (count, value), and pop the root whenever len(min_heap) > k. The root is the least frequent of the k + 1 kept, so it can never be in the answer.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Heap direction: the k most frequent need a min-heap, because
heappopremoves the root; a max-heap of size k would evict the most frequent value.Heap ordering: push tuple
(freq, num)so heap orders by frequency, not number value.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd use a Top-K Heap. First I count each value with a Counter. Then I walk the counts and push each (count, value) pair onto a min-heap, and whenever the heap grows past k, I pop its root. The root is the least frequent of the k + 1 items kept, and k others already beat it, so it can never be in the answer. After the last push, the heap holds exactly the k most frequent values. The trap is the direction: to keep the k largest I need a min-heap, because its root is the item I evict next; a max-heap would throw away the winner. Counting is
O(N)and each push or pop is O(log K), so the time isO(N log K), withO(N)space for the counts plus O(K) for the heap."
Complexity & Mathematical Proof
O(N log K)
Look at the execution steps: Frequency hash map takes O(N) to build. Iterates through unique elements and maintains min-heap of size K: each push/pop costs O(log K). Total O(N log K) time (or O(N) via bucket sort).
O(N) counts + O(K) heap
Look at memory allocations: Call stack uses O(1) Iterative. Hash map of size N and min-heap of size K.
T(N, K) = O(N) + N · O(log K) = O(N log K)
Derivation Progression
O(N) linear hash map tally
Counts occurrences of each number in array.
U unique keys × O(log K) min-heap push/pop
Maintains the top K highest frequency elements.
O(N log K) ≤ O(N log N)
Optimal when K << N.
Variable Definitions
Total number of elements in the array
Number of top frequent elements requested (min-heap capacity)
Number of unique elements in the array (U ≤ N)
Memory Architecture & Bounds
O(1) Iterative
O(N) counts + O(K) heap
O(K) List of top K frequent elements
Boundary Best / Worst Cases
if K=1 or all elements identical.
.
with all unique elements.
Binary Heap Priority Queue Tree
Senior SWE Deconstruction & Hardware Caveats
Key triggers: "the k values that appear most often", "any order", and the follow-up to beat a full sort. Only the top k of many counted keys matter, so a Top-K Heap keeps k of them and throws the rest away as it goes.
and , so there are at most distinct values, and can be as large as . After the count the heap does at most pushes and pops of each: , inside the bound.
Heap direction: keeping the k largest needs a min-heap, because its root is the item evicted next; a max-heap pops the winner. When k is close to U, the heap saves little and sorting the counts (or bucketing by count, ) is simpler.
Core Algorithmic State Invariants
- One Push per Distinct Value
The loop runs over counts.items(), so the heap sees each distinct value once, not each element: with -10^4 <= nums[i] <= 10^4 there are at most 2 * 10^4 + 1 pushes, even when nums holds 10^5 numbers.
- Why the Unique-Answer Promise Matters
LeetCode promises the answer is unique, so the k-th and (k+1)-th counts are never tied at the cut. Without that promise, two values with the same count could compete for the last seat, and which one heappop evicts would depend only on the value used as the tie-breaker.
- Any Order Is Accepted
The answer is read straight out of min_heap with [value for count, value in min_heap], in heap order rather than sorted order. That is enough because the problem accepts the k values in any order, so no final sort is needed.
Top K Frequent Elements (LeetCode 347)
You're given an integer array nums and an integer k. Report the k values that appear most often in nums — ties in return order don't matter, so any ordering of the k values is accepted.
Follow-up: a full O(n log n) sort is accepted, but can you do better? Aim for a time complexity below O(n log n), where n is the length of nums.
Worked Examples
nums = [1,1,1,2,2,3], k = 2[1,2]1 appears 3 times and 2 twice, more often than 3.nums = [1], k = 1[1]nums = [1,2,1,2,1,2,3,1,3,2], k = 2[1,2]1 and 2 appear 4 times each; 3 appears only twice.⚖️Formal Constraints & Bounds
1 <= nums.length <= 105-104 <= nums[i] <= 104kis in the range[1, the number of unique elements in the array].It is guaranteed that the answer is unique.
Core Insight
Bounding the heap to size K ensures all push/pop heap operations take O(log K) rather than O(log N) time.
Real-World Scenario & Production Applications
Real-time analytics trending topics (Twitter/X hashtag rankings) and cache eviction telemetry.
Subproblems & Recurrence Decomposition3 Phases
Count element frequencies in O(N) time using a hash map count = Counter(nums).
count = Counter(nums)Step-by-Step Execution Trace Table
| Step | Item Pushed (freq, val) | Min-Heap State After Push | Size | Over k = 2? | Evicted Root | Heap State After Step |
|---|---|---|---|---|---|---|
| 1 | (3, 1) | [(3, 1)] | 1 | No | — | [(3, 1)] |
| 2 | (2, 2) | [(2, 2), (3, 1)] | 2 | No | — | [(2, 2), (3, 1)] |
| 3 | (1, 3) | [(1, 3), (3, 1), (2, 2)] | 3 | Yes | (1, 3) (lowest freq) | [(2, 2), (3, 1)] |
| 1 | counts = Counter(nums) |
| 2 | min_heap = [] |
| 3 | for value, count in counts.items(): |
| 4 | heappush(min_heap, (count, value)) |
| 5 | if len(min_heap) > k: |
| 6 | heappop(min_heap) |
| 7 | return [value for count, value in min_heap] |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Identifying the $K$ most frequent elements requires counting occurrences with a hash map and then extracting the $K$ highest frequencies. Maintaining a min-heap of capacity $K$ keyed by frequency ensures that the smallest frequency among the current top $K$ sits at the root. Evicting the root whenever size exceeds $K$ bounds runtime to $O(N \log K)$ and space to $O(N + K)$. 🏆 The Analogy: A Leaderboard With Only k Seats
Imagine a leaderboard with exactly k seats, currently occupied by whoever has qualified so far. A new contender only earns a seat by beating the weakest person currently on the board — and the moment they do, the weakest person gets bumped off. You never need to compare a new contender against everyone in the whole competition, only against the single weakest name currently on the board, which a min-heap hands you instantly.
🔑 The Key Idea in the Code
A min-heap (not a max-heap) is the right tool specifically because the operation you need repeatedly is "find and remove the smallest" — the weakest current qualifier — not the largest.
Sorting full dictionary : Sorting all unique elements by frequency is . A min-heap of size keyed on frequency maintains the top in , and bucket sort achieves .
Inverting heap key ordering: Storing
(key, freq)in Python's min-heap sorts primarily bykey. Always store(freq, key)so the heap prioritizes frequency.Popping from min-heap leaves root as smallest: In a min-heap of size , the elements left in the heap at the end are the most frequent, but popped in ascending order. Reverse if descending order is requested.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Find top / most frequent K elements from unsorted data.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Decision rule: push every (count, value), and pop the root whenever len(min_heap) > k. The root is the least frequent of the k + 1 kept, so it can never be in the answer.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Heap direction: the k most frequent need a min-heap, because
heappopremoves the root; a max-heap of size k would evict the most frequent value.Heap ordering: push tuple
(freq, num)so heap orders by frequency, not number value.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd use a Top-K Heap. First I count each value with a Counter. Then I walk the counts and push each (count, value) pair onto a min-heap, and whenever the heap grows past k, I pop its root. The root is the least frequent of the k + 1 items kept, and k others already beat it, so it can never be in the answer. After the last push, the heap holds exactly the k most frequent values. The trap is the direction: to keep the k largest I need a min-heap, because its root is the item I evict next; a max-heap would throw away the winner. Counting is
O(N)and each push or pop is O(log K), so the time isO(N log K), withO(N)space for the counts plus O(K) for the heap."
Complexity & Mathematical Proof
O(N log K)
Look at the execution steps: Frequency hash map takes O(N) to build. Iterates through unique elements and maintains min-heap of size K: each push/pop costs O(log K). Total O(N log K) time (or O(N) via bucket sort).
O(N) counts + O(K) heap
Look at memory allocations: Call stack uses O(1) Iterative. Hash map of size N and min-heap of size K.
T(N, K) = O(N) + N · O(log K) = O(N log K)
Derivation Progression
O(N) linear hash map tally
Counts occurrences of each number in array.
U unique keys × O(log K) min-heap push/pop
Maintains the top K highest frequency elements.
O(N log K) ≤ O(N log N)
Optimal when K << N.
Variable Definitions
Total number of elements in the array
Number of top frequent elements requested (min-heap capacity)
Number of unique elements in the array (U ≤ N)
Memory Architecture & Bounds
O(1) Iterative
O(N) counts + O(K) heap
O(K) List of top K frequent elements
Boundary Best / Worst Cases
if K=1 or all elements identical.
.
with all unique elements.
Binary Heap Priority Queue Tree
Senior SWE Deconstruction & Hardware Caveats
Key triggers: "the k values that appear most often", "any order", and the follow-up to beat a full sort. Only the top k of many counted keys matter, so a Top-K Heap keeps k of them and throws the rest away as it goes.
and , so there are at most distinct values, and can be as large as . After the count the heap does at most pushes and pops of each: , inside the bound.
Heap direction: keeping the k largest needs a min-heap, because its root is the item evicted next; a max-heap pops the winner. When k is close to U, the heap saves little and sorting the counts (or bucketing by count, ) is simpler.
Core Algorithmic State Invariants
- One Push per Distinct Value
The loop runs over counts.items(), so the heap sees each distinct value once, not each element: with -10^4 <= nums[i] <= 10^4 there are at most 2 * 10^4 + 1 pushes, even when nums holds 10^5 numbers.
- Why the Unique-Answer Promise Matters
LeetCode promises the answer is unique, so the k-th and (k+1)-th counts are never tied at the cut. Without that promise, two values with the same count could compete for the last seat, and which one heappop evicts would depend only on the value used as the tie-breaker.
- Any Order Is Accepted
The answer is read straight out of min_heap with [value for count, value in min_heap], in heap order rather than sorted order. That is enough because the problem accepts the k values in any order, so no final sort is needed.