Q29: Top K Frequent Elements
Given an integer array nums and an integer k, return the $k$ most frequent elements. Solve it in $O(n)$ time using Bucket Sort.
Bucket Sort Top K Frequent
function topKFrequent(nums, k) {
const map = new Map();
for (let num of nums) {
map.set(num, (map.get(num) || 0) + 1);
}
const buckets = Array.from({ length: nums.length + 1 }, () => []);
for (let [num, freq] of map) {
buckets[freq].push(num);
}
const result = [];
for (let i = buckets.length - 1; i >= 0 && result.length < k; i--) {
if (buckets[i].length > 0) {
result.push(...buckets[i]);
}
}
return result.slice(0, k);
}
console.log(topKFrequent([1,1,1,2,2,3], 2)); // [1, 2]💡 Counts occurrences in a Map, uses array indices as frequency buckets, and iterates backward from maximum possible frequency to extract top k items.
Key Takeaways
- Bucket Sort groups elements into array indices matching their exact frequency count.
- Achieves $O(n)$ linear time complexity, beating $O(n \log n)$ heap/sorting methods.
Knowledge Check
What determines the size of the buckets array in this Bucket Sort implementation?