Appearance
4.4.5 — Top K Frequent Elements
LeetCode 347 · Medium · ★ Blind 75
The problem
You are given a list of numbers called nums and a number k. Return the k values that appear most often in the list. You may return them in any order.
nums = [1, 1, 1, 2, 2, 3], k = 2 → [1, 2]
nums = [1], k = 1 → [1]In the first example, 1 appears three times, 2 appears twice and 3 appears once. The two most frequent values are 1 and 2.
The list has up to 100,000 numbers. The problem promises the answer is unique, so there is never a tie at the cut-off. It also asks for something faster than O(n \log n), read "order n log n". That last request is the real point of the problem.
What the problem is really asking
There are two questions stacked on top of each other.
- How many times does each value appear? This is a counting job, and you already know how to do it with a hash map.
- Which
kof those counts are the biggest? This is a selection job. It is the interesting part, and it has three good answers.
The first question is the same in every solution:
python
from collections import Counter
count = Counter(nums) # {1: 3, 2: 2, 3: 1}Counter walks the list once and builds a map from each value to how many times it appeared.
The brute force, and where it wastes work
Sort the values by their count, biggest first, and take the first k.
python
count = Counter(nums)
ranked = sorted(count.keys(), key=lambda v: count[v], reverse=True)
return ranked[:k]key=lambda v: count[v] tells sorted to order the values by their counts. reverse=True puts the biggest first. [:k] keeps the first k.
If there are u different values, this sort takes O(u \log u) time. In the worst case every value is different, so u = n and it is O(n \log n). That is exactly what the problem asks us to beat.
The waste in one sentence: the sort puts every value in its exact rank, but we only asked which values are in the top k.
Think of a marathon with 10,000 runners. To hand out three medals, you do not need to know who came 5,000th and who came 5,001st. Sorting the whole field is doing that unneeded work.
Solution 1 — keep only k candidates, using a heap
A heap is a structure that always keeps its smallest item at the front, where you can see it or remove it quickly. Adding an item or removing the smallest item takes O(\log m) steps for a heap holding m items. Python's heapq module gives you this. 4.16 explains how it works inside.
The plan: walk through the counts, and keep a heap of at most k values. Whenever the heap grows past k, throw out the weakest one.
python
import heapq
from collections import Counter
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
count = Counter(nums) # (1)
heap = [] # (2)
for value, freq in count.items(): # (3)
heapq.heappush(heap, (freq, value)) # (4)
if len(heap) > k: # (5)
heapq.heappop(heap) # (6)
return [value for freq, value in heap] # (7)(1) Count every value, as described above.
(2) An empty heap. It will hold the best k candidates seen so far.
(3) Walk through each distinct value and its count.
(4) Push the pair (freq, value). Python compares pairs from left to right, so the heap orders them by frequency first. The value is there so we can read it back at the end.
(5) and (6) If the heap now holds more than k items, remove the smallest one, which is the one with the lowest frequency. It can never be in the top k, because there are already k values with a higher count.
(7) What is left in the heap is the top k. We return just the values.
Why a heap that keeps the smallest at the front, when we want the largest values? People get this backwards, so here is the reason. A heap only lets you reach one end cheaply. The item we keep needing to reach is the weakest of the ones we are keeping, because that is the one a stronger newcomer replaces. A heap with the smallest at the front puts exactly that item where we can reach it.
Complexity. Counting takes O(n). Then each of the u distinct values is pushed once, and maybe popped once, into a heap that never holds more than k + 1 items. Each push or pop costs O(\log k). So that part is O(u \log k), and the total is O(n + u \log k). When k is small, \log k is tiny, and this is much better than sorting. The extra memory is the map, O(u), plus the heap, O(k).
This version has one more strength. It only ever keeps k items in the heap, and it looks at each value once. So it also works on a stream, which is data that keeps arriving and is too big to hold all at once.
Python has this built in as Counter(nums).most_common(k). It uses a heap of size k inside.
Solution 2 — buckets by frequency, in linear time
Here is the observation that gives us O(n):
No value can appear more than n times. The list only has n numbers in it.
So every count is a whole number between 1 and n. When the things you want to order are small whole numbers with a known limit, you do not need to sort them at all. You can use each count as a position in a list.
Make a list of "buckets", one bucket for each possible count from 0 to n. Put every value into the bucket matching its count. Then walk the buckets from the biggest count down, and collect values until you have k.
Read the figure from left to right first. Each bucket's number is a count. The value inside a bucket is a value that appeared that many times. Buckets 4, 5 and 6 are empty because no value appeared that often. Then follow the arrow from right to left. That is the walk: it skips the empty buckets, collects 1, collects 2, and stops because it has k = 2 values.
python
from collections import Counter
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
count = Counter(nums) # (1)
buckets = [[] for _ in range(len(nums) + 1)] # (2)
for value, freq in count.items(): # (3)
buckets[freq].append(value)
result = [] # (4)
for freq in range(len(buckets) - 1, 0, -1): # (5)
for value in buckets[freq]: # (6)
result.append(value)
if len(result) == k: # (7)
return result
return result # (8)ts
function topKFrequent(nums: number[], k: number): number[] {
const count = new Map<number, number>(); // (1)
for (const n of nums) count.set(n, (count.get(n) ?? 0) + 1);
const buckets: number[][] =
Array.from({ length: nums.length + 1 }, () => []); // (2)
for (const [value, freq] of count) buckets[freq].push(value); // (3)
const result: number[] = []; // (4)
for (let freq = buckets.length - 1; freq >= 1; freq--) { // (5)
for (const value of buckets[freq]) { // (6)
result.push(value);
if (result.length === k) return result; // (7)
}
}
return result; // (8)
}Line by line
(1) Count every value. In TypeScript there is no Counter, so we build the map by hand. count.get(n) ?? 0 means "the current count, or 0 if this value is new". The ?? operator picks the right side when the left side is missing.
(2) Make n + 1 empty buckets. Bucket number f will hold every value that appeared exactly f times. Why n + 1 buckets, and not n? Because if every number in the list is the same, that value appears n times, so bucket number n must exist. Lists start counting at 0, so reaching position n needs n + 1 slots. Bucket 0 stays empty, since every value we count appeared at least once.
This line hides the most common bug on the page. In Python, do not write [[]] * (len(nums) + 1). That does not make many lists. It makes one list and fills every slot with a reference to that same list. Adding a value to bucket 3 would then add it to every bucket. The form [[] for _ in range(...)] runs [] again for each slot, so each slot gets its own new list.
JavaScript has the same trap. new Array(n).fill([]) fills every slot with the same array. Array.from({ length: n }, () => []) calls the little function once per slot, so each slot gets a fresh array.
(3) Drop each value into its bucket. A value that appeared 3 times goes into buckets[3].
(4) An empty result list.
(5) Walk the buckets from the highest count down to 1. range(len(buckets) - 1, 0, -1) counts down from n to 1. The third number, -1, means "step backwards". We start at the top because we want the most frequent values first.
(6) Take every value in this bucket. A bucket can hold several values if they share a count.
(7) Stop as soon as we have k values. There is no need to look at the lower buckets.
(8) The fallback return. This line runs only when the walk finishes without reaching k. That happens when k equals the number of distinct values, because the last value is added in the last bucket of the walk and then the loop simply ends. So this line is not dead code.
Trace
Take nums = [1, 1, 1, 2, 2, 3] and k = 2. There are 6 numbers, so we make 7 buckets, numbered 0 to 6.
After lines (1) to (3): bucket 1 holds [3], bucket 2 holds [2], bucket 3 holds [1]. All other buckets are empty.
freq | Bucket contents | Action | result |
|---|---|---|---|
| 6 | [] | nothing | [] |
| 5 | [] | nothing | [] |
| 4 | [] | nothing | [] |
| 3 | [1] | add 1 | [1] |
| 2 | [2] | add 2, now 2 values | [1, 2] → return |
The answer is [1, 2].
Complexity, derived
Time. Line (1) visits all n numbers once: O(n). Line (2) makes n + 1 buckets: O(n). Line (3) visits each of the u distinct values once: O(u).
The walk in lines (5) to (7) looks like a loop inside a loop, which often means n \times n. It is not, here. The outer loop visits n buckets. The inner loop visits the values in one bucket. But every distinct value sits in exactly one bucket. So across the whole walk, the inner loop touches each value at most once, u times in total. The outer loop adds n steps for the buckets themselves. That is O(n + u).
Adding everything: O(n) + O(n) + O(u) + O(n + u). Since u can never be bigger than n, all of this is O(n).
Space. The count map holds u entries. The buckets list has n + 1 slots, and the values inside all the buckets add up to u. So the extra memory is O(n).
Which solution to give
In an interview, present all three as a ladder, then write the one they want.
- Sorting is O(n \log n). Simple, and the thing you are asked to beat.
- The heap is O(n + u \log k). Best when
kis small, and the only one that works on a stream. - Buckets is O(n). It meets the stated requirement.
Buckets have one real downside. They always make n + 1 buckets, even when there are only three distinct values. If n is huge and u is tiny, the heap uses far less memory.
Edge cases
kequals the number of distinct values. The walk collects every value and ends through line (8).- Negative numbers. They are fine. They are only keys in the map. Only the counts are used as bucket positions, and counts are never negative.
- A single number, such as
[1]withk = 1. Bucket 1 holds[1]and the answer is[1].
Variations you will meet
- Top K Frequent Words. The same problem, but ties must be broken in alphabetical order. That rule means order inside a bucket now matters, so both fast solutions need extra care.
- Kth Largest Element in an Array. Selection without the counting step. It has a fourth answer called quickselect, which is O(n) on average. See 4.17.4.
- Too much data to count exactly. A Count-Min sketch estimates counts using a small, fixed amount of memory. See 4.29.
The general lesson: when the thing you order by is a small whole number with a known limit, do not sort. Use it as a list position. Counting sort, radix sort and this problem all rest on that one idea.
What the interviewer will push on
"Can you beat O(n \log n)?" They are waiting for one sentence: "A count can never be bigger than n, so the counts are small whole numbers, and I can use them as list positions."
"Why does the heap keep the smallest at the front, if you want the largest?" They are checking that you know what sits at the front: the weakest kept item, which is the one you will throw out next.
"What if k is close to the number of distinct values?" The heap grows to nearly u items and becomes O(u \log u), no better than sorting. Buckets do not care about k.
"What if the data is a stream?" Only the heap works, because it never needs the whole list. If even the count map is too big, use a Count-Min sketch.
One thing to volunteer: explain why the nested walk in lines (5) to (7) is linear and not quadratic. Each value lives in exactly one bucket, so the inner loop touches it once in total.
Next: 4.4.6 Encode and Decode Strings. A design question rather than a counting one.