ASAPUtils
The signal
“k most frequent” is two patterns stacked: count the frequencies, then select the top k. Counting is a hash map. Selection is where the interesting decision is — and it’s the one place where noticing a bound buys you a whole complexity class.
Approach ladder
1. Count, then sort — O(n log n)
Build the frequency map, dump it into an array, sort descending by count, take the first k. Obvious, correct, and the thing to say first.
2. Count, then heap — O(n log k)
Push into a min-heap of size k; whenever it exceeds k, pop the smallest. This is the classic “top-k” answer and it’s what most people stop at. It’s genuinely good — and it’s still not the best here.
3. What are both wasting?
They’re comparing frequencies. But look at the range: a frequency is an integer between 1 and n. Values that small and dense don’t need comparing — they can be used directly as array indices. That observation is the whole problem.
4. Optimal — bucket by count, O(n)
Make an array buckets of length n + 1, where buckets[f] holds every value that appeared
exactly f times. Then walk from f = n down to 1, collecting until you have k.
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int,int> freq;
for (int x : nums) freq[x]++;
vector<vector<int>> buckets(nums.size() + 1);
for (auto& [val, f] : freq) buckets[f].push_back(val);
vector<int> res;
for (int f = nums.size(); f >= 1 && (int)res.size() < k; f--)
for (int val : buckets[f]) {
res.push_back(val);
if ((int)res.size() == k) break;
}
return res;
}
function topKFrequent(nums, k) {
const freq = new Map();
for (const x of nums) freq.set(x, (freq.get(x) ?? 0) + 1);
const buckets = Array.from({ length: nums.length + 1 }, () => []);
for (const [val, f] of freq) buckets[f].push(val);
const res = [];
for (let f = nums.length; f >= 1 && res.length < k; f--)
for (const val of buckets[f]) {
res.push(val);
if (res.length === k) break;
}
return res;
}
Why the buckets array is only n+1 long
Because a value cannot appear more times than there are elements. That single bound is what makes indexing-by-frequency legal, and it’s the transferable idea: when a quantity is bounded by n, you can index by it instead of sorting by it. The same reasoning powers counting sort.
Complexity
- Time O(n) — one pass to count, one to bucket, one partial walk down.
- Space O(n) — map plus buckets.
Traps
- Sizing the buckets array
ninstead ofn + 1. A value appearing all n times needs index n. - Walking buckets upward. You want the highest frequencies first.
- Not breaking once you have k. Correct but sloppy, and it shows.
Blank re-solve prompt
Given an array and k, return the k most frequent values in O(n) time — no sorting and no heap.