Top K Frequent Elements

Problem

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

 

Example 1:

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

Example 2:

Input: nums = [1], k = 1
Output: [1]

 

Constraints:

• 1 <= nums.length <= 105
• k is in the range [1, the number of unique elements in the array].
• It is guaranteed that the answer is unique.

Solution

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
    // store frequency of each value in nums
    const map = {};
    for (const n of nums) {
        if (!(n in map)) {
            map[n] = 0;
        }
        map[n]++;
    }

    // bucket sort by frequency
    const bucket = [];
    for (const key in map) {
        const freq = map[key];
        while (bucket.length <= freq) {
            bucket.push([]);
        }
        bucket[freq - 1].push(key);
    }

    // retrieve k most frequent elements from bucket
    const res = [];
    for (let i = bucket.length - 1; res.length < k; i--) {
        res.push(...bucket[i]);
    }

    return res;
};

We store the frequency for each value in nums using hashmap map, use bucket sort based on the frequency stored in map (where bucket[i] contains values with occurrence i - 1), and finally retrieve the k values starting from the back of bucket.