Top K Frequent Elements

Problem Statement

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Example:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Approach: Bucket Sort

A brute force approach involves counting the frequencies, sorting the elements by frequency in descending order, and picking the top $k$. This takes $O(n \log n)$ time.

However, we can optimize this to $O(n)$ time using a variation of Bucket Sort. Since the maximum possible frequency of any element is bounded by the length of the array n, we can use an array where the indices represent the frequencies, and the values are lists of numbers that occur at that frequency.

1. First, create a Hash Map to count the frequency of every element in the array nums.
2. Create an array called bucket of size nums.length + 1. Initialize each element as an empty array. The index i of this array will represent a frequency of i.
3. Iterate through your Hash Map. For every [num, freq] pair, push the num into the array at bucket[freq].
4. Create an empty result array.
5. Iterate through the bucket array backwards (starting from the highest possible frequency down to 0).
6. Whenever you find numbers in a bucket, add them to your result array.
7. Stop collecting and return the result array as soon as its length reaches k.

Solution

function topKFrequent(nums, k) {
    const count = {};
    const bucket = Array.from({ length: nums.length + 1 }, () => []);
    const result = [];
    
    // Step 1: Count frequencies
    for (let num of nums) {
        count[num] = (count[num] || 0) + 1;
    }
    
    // Step 2: Populate the buckets
    for (let num in count) {
        const freq = count[num];
        bucket[freq].push(Number(num));
    }
    
    // Step 3: Gather the top k frequent elements
    for (let i = bucket.length - 1; i >= 0; i--) {
        if (bucket[i].length > 0) {
            result.push(...bucket[i]);
            if (result.length === k) {
                return result;
            }
        }
    }
    
    return result;
}

Complexity Analysis

• Time Complexity: $O(n)$ where $n$ is the total number of elements in the input array. We iterate through the array once to count frequencies, once through the unique elements to fill the buckets, and in the worst case, we traverse the bucket array of size $n+1$. All operations are linear.
• Space Complexity: $O(n)$. The Hash Map takes up to $O(n)$ space if all elements are unique. The bucket array also requires $O(n)$ space to store the elements across different frequency indices.