LC 347 Top K Frequent Elements

Implementation

// 347. Top K Frequent Elements
// 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]

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

// 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.

var topKFrequent = (nums, k) => {
    // hashing
    const arrFreq = new Map();
    for(let num of nums){
        arrFreq.set(num,(arrFreq.get(num)||0)+1)
    }
    // bucket sort
    const arr = new Array(nums.length+1);
    for(let [key,value] of arrFreq){
        if (!arr[value]) arr[value] = [];
            arr[value].push(key);
    }
    let res = [];
    for(let i=nums.length;i>0;i--){
        if(arr[i]){
            res.push(...arr[i]);
            if(res.length===k) return res;
        }
    }
};
console.log(topKFrequent([1,1,1,2,2,3],2))
console.log(topKFrequent([1], 1))
console.log(topKFrequent([1,2,1,2,1,2,3,1,3,2], 2))

Tests

// Test stub for 01.347.TopKFrequentElements

describe('01.347.TopKFrequentElements', () => {
  it('should have a test stub', () => {
    expect(true).toBe(true);
  });
});