cheatsheet1999/FrontEndCollection

Top K Frequent Elements

cheatsheet1999 opened this issue · 0 comments

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

Screen Shot 2021-09-07 at 6 43 26 PM

var topKFrequent = function(nums, k) {
    const map = new Map();
    const res = [];
    const freqArr = [];
    
    for(let num of nums) {
        map.set(num, (map.get(num) || 0) + 1);
    }
    
    for(let [num, freq] of map) {
        freqArr[freq] = (freqArr[freq] || new Set()).add(num);
    }
    
    for(let i = freqArr.length - 1; i >= 0; i--) {
        // if(freqArr[I]) is necessary because not all index has element attached to it
        if(freqArr[i]) res.push(...freqArr[i]);
        if(res.length === k) break;
    }
    return res;
};

Time complexity : O(n)