347. 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
• -104 <= nums[i] <= 104
• k is in the range [1, the number of unique elements in the array].
• It is guaranteed that the answer is unique.

Solution

First attempt : (Can be optimized further)

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
    let frequency = {};
    let output = [];
    for(let i = 0; i < nums.length; i++){
        if(nums[i] in frequency){
            frequency[nums[i]] = frequency[nums[i]] + 1;
        }
        else{
            frequency[nums[i]] = 1;
        }
    }
for(let i = 1; i <= k; i++ ){
    let max = 0;
    let maxvalue = "";
    for(let [key,value] of Object.entries(frequency)){
        if(max < value){
            max = value;
            maxvalue = key;
        }
        
    }
    frequency[maxvalue] = 0;
    output.push(maxvalue);
}

    return output;
};

Optimized solution:

var topKFrequent = function(nums, k) {
    const frequency = new Map();
    const buckets = new Array(nums.length + 1).fill(null).map(() => []);

    // Count the frequency of each element
    for (const num of nums) {
        frequency.set(num, (frequency.get(num) || 0) + 1);
    }

    // Place elements in the corresponding bucket
    for (const [num, freq] of frequency.entries()) {
        if (!buckets[freq]) {
            buckets[freq] = [];
        }
        buckets[freq].push(num);
    }

    // Extract the top k frequent elements
    const result = [];
    for (let i = buckets.length - 1; i >= 0 && result.length < k; i--) {
        if (buckets[i] && buckets[i].length > 0) {
            result.push(...buckets[i]);
        }
    }

    return result.slice(0, k);
};