Learning Outcome
After this lesson, you should be able to combine a frequency map with a size-k heap to rank values.
Problem Statement
Given an integer array and k, return the k elements that appear most frequently.
| Input | Output | Why |
|---|---|---|
nums = [1,1,1,2,2,3], k = 2 | [1,2] | 1 appears three times and 2 appears twice. |
Brute Force Approach
Count frequencies, then sort every unique value by frequency. This works but costs extra sorting time.
Optimized Approach
Count frequencies and maintain a min-heap of size k by frequency. The heap discards lower-frequency values.
Exact Pseudocode
freq = value counts
heap = empty min heap by frequency
for each value and count:
push (count, value)
if heap size is greater than k:
pop smallest frequency
return values from heapReference Code
import heapq
from collections import Counter
class Solution:
def topKFrequent(self, nums, k):
heap = []
for value, count in Counter(nums).items():
heapq.heappush(heap, (count, value))
if len(heap) > k:
heapq.heappop(heap)
return [value for count, value in heap]Sample Dry Run
| Step | State | Result |
|---|---|---|
| Count | 1:3, 2:2, 3:1 | Frequency map ready |
| Push 1 and 2 | heap size is 2 | Both remain |
| Push 3 | frequency 1 is smallest | 3 is popped |
| Return | heap has 1 and 2 | top k frequent values |
Complexity
| Measure | Value | Reason |
|---|---|---|
| Time | O(n + m log k) | n counts input values and m unique values are processed by the heap. |
| Space | O(m) | The frequency map stores m values and the heap stores k values. |
Edge Cases
- If k equals the number of unique values, return all unique values.
- Output order is usually not important unless specified.
- Values can be negative or repeated many times.
Interview Checklist
- Heap must rank by frequency, not raw value.
- Keep heap size at most k.
- Build the frequency map before ranking.
FAQs
Why use a min-heap?
The smallest frequency among the current top k should be easiest to remove.
What does m mean?
m is the number of unique values in the input.
What is the core pattern?
Frequency map plus size-k heap.