Top K Frequent Elements

medium

Array Bucket Sort

<Code />

function topKFrequent(nums, k) {
    // Count the frequency of each number
    let counts = {};
    for (let n of nums) {
        counts[n] = (counts[n] || 0) + 1;
    }

    // Create buckets for each frequency and collect numbers
    let buckets = Array.from({ length: nums.length + 1 }, () => []);
    for (let n in counts) {
        buckets[counts[n]].push(n);
    }

    // Collect the top k frequent elements
    let res = [];
    for (let i = buckets.length - 1; i > 0 && res.length < k; i--) {
        for (let n of buckets[i]) {
            res.push(n);
        }
    }

    return res;
}

Thoughts

This problem would usually be solved with a heap by collecting the frequencies, and storing them in a heap. Here, though, we are using buckets to store the counts of each number. It's a clever trick.