Part 2 · Problems · Arrays and hashing
Top K Frequent Elements
#347 · Medium · LeetCode
Return the k most frequent numbers.
[1,1,1,2,2,3], k = 2 -> [1,2]
Ask before coding
- Any order in the output?
- Ties?
Hint
Count first. A count can't be bigger than n.
Approach
Count with a Map. Then bucket by count: bucket[c] holds numbers seen c times. Walk buckets from high to low until you have k.
Time O(n) Space O(n)
Watch it run
Solution (JavaScript, tested)
function topKFrequent(nums, k) {
const count = new Map();
for (const n of nums) count.set(n, (count.get(n) ?? 0) + 1);
// bucket[i] = numbers that appear exactly i times
const bucket = Array.from({ length: nums.length + 1 }, () => []);
for (const [n, c] of count) bucket[c].push(n);
const out = [];
for (let c = bucket.length - 1; c > 0 && out.length < k; c--) out.push(...bucket[c]);
return out.slice(0, k);
}Traps
- Sorting the counts is O(n log n). Fine to say first, then improve.
- A heap of size k gives O(n log k).
Say out loud: Count, then I need the top k. Sorting is n log n. Since counts are bounded by n, bucket sort makes it linear.