Top K Frequent Elements
Count, then select the k largest — a heap or bucket sort beats a full sort.
Heap Trace
Problem
Given an integer array and an integer k, return the k distinct values that occur most often in the array. The answer may be returned in any order, and the input is guaranteed to contain at least k distinct values.
Examples
Input: nums = [4,1,-1,2,-1,2,3], k = 2
Output: [-1,2]
Input: nums = [5,5,5,2,2,8], k = 1
Output: [5]
The Goal
Return the k values that appear most often in nums, in any order.
For [4, 1, -1, 2, -1, 2, 3] and k = 2, -1 and 2 appear twice and the rest once, so the answer is [-1, 2].
Where a value sits doesn't matter, only how often it appears. Count each value first, then pick the k biggest counts.
Count, then select
Turn the list into one count per distinct value, then keep the k values with the biggest counts.
Count once, then select without sorting every count.
Key Idea: A Heap of (count, value) Pairs
Push each value as a pair (count, value) onto a min-heap. Python compares pairs by count first, so the least frequent sits at the root.
When the heap holds k + 1 pairs, pop the root. What's left is the k most frequent so far. On a tie in count, the pair with the smaller value is smaller, so it pops first.
| Approach | Time | How |
|---|---|---|
| Sort every count | O(n log n) | Orders values you never return |
| Min-heap of size k | O(n log k) | Keeps only the k most frequent |
| Buckets by count | O(n) | Bucket c holds the values seen c times |
The Algorithm
import heapq
from collections import Counter
def top_k_frequent(nums, k):
count = Counter(nums)
heap = []
for value, c in count.items():
heapq.heappush(heap, (c, value))
if len(heap) > k:
heapq.heappop(heap)
return [value for c, value in heap]Counter keeps values in the order they first appear, so the loop visits them in that order. The answer comes out in heap order, which LeetCode accepts.
Buckets reach O(n): put each value in the bucket for its count, then read buckets from the highest count down until you have k.
Walkthrough
Run it on [4, 1, -1, 2, -1, 2, 3] with k = 2. In order, 4 appears once, 1 once, -1 twice, 2 twice and 3 once.
(1, 4) and (1, 1) fill the heap. (2, -1) makes three, and (1, 1) pops: it ties with (1, 4) on count, and 1 is smaller. (2, 2) pushes out (1, 4), and (1, 3) pops right back out. The heap ends as [(2, -1), (2, 2)].
Checkpoint · predict the next step
Step 6 of 16 on the stage: Push (1, 1). The heap holds 2, no more than k = 2. The least frequent, (1, 1), is at the root.
heap = ["1 1", "1 4"] · k 2 · seen 1 of 5
Pitfalls
- Push
(count, value), not(value, count). The heap orders by the first item. - Pop only when the heap holds more than
k. - With
kor fewer distinct values, nothing pops and every value comes back. - A tie at the cut, as in
[1, 1, 2, 2, 3, 3]withk = 2, keeps the larger values:[2, 3]. LeetCode rules such inputs out.
Why is sorting every count a weaker choice?
Complexity
Counting takes O(n). With m distinct values, the heap does m pushes and at most m pops, each O(log k), so time is O(n + m log k), at most O(n log k).
The counts take O(m) space and the heap O(k). Buckets trade the heap for n + 1 lists and run in O(n).
Count, then a heap of size k
- Count valuesOne update per number.O(n)
- Push and pop pairsm distinct values.O(m log k)
- Counts and heapOne count per value.O(n)
- Buckets insteadn + 1 lists, no heap.O(n)
A heap of k pairs skips the full sort.
In short
Tally frequencies with a hash map. To pick the top k, either push counts into a size-k min-heap (O(n log k)) or bucket-sort by frequency into indices 0..n and read from the top (O(n)). Bucket sort wins when k approaches n.
Common mistake
Sorting all counts (O(n log n)) when you only need the top k — a heap or buckets is asymptotically better.