Posts published in “Heap”

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

Solution 1: Bucket Sort O(n); O(n)

• Use a HashMap to store each number and its frequency.
• Use bucket array to save numbers into different bucket whose index is the frequency

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
    let counts = new Map();
    let buckets = [];
    for (let i = 0; i <= nums.length; i++)
        buckets.push([]);
    
    // count frequent of the elements
    for (let num of nums) {
        if (counts.has(num)) {
            counts.set(num, counts.get(num) + 1);
        } else {
            counts.set(num, 1);
        }
    } 
    // put them into buckets by frequent
    for (let [key, value] of counts) {
        buckets[value].push(key);
    }
    // fetch the larget frequest bucket first, until reach k
    let ans = [];
    for (let i = buckets.length - 1; i > 0 && ans.length < k; i--) {
        if (buckets[i] !== null) ans.push(...buckets[i]);
    }
    return ans;
};

Solution 2: maxHeap O(n log n); O(n)

Javascript does not have a standard heap / priority queue data structure that you can use out of the box.

See Java solution:

public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> res = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return res;
        }

        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        PriorityQueue<Map.Entry<Integer, Integer>> maxHeap = new 
            PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            maxHeap.offer(entry);
        }

        while (res.size() < k) { //important
            res.add(maxHeap.poll().getKey());
        }
        return res;
    }

Solutoin 3: TreeMap (n log n); O(n)

Use treeMap. Use freqncy as the key so we can get all freqencies in order

See Java solution:

public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int n: nums){
            map.put(n, map.getOrDefault(n,0)+1);
        }

        TreeMap<Integer, List<Integer>> freqMap = new TreeMap<>();
        for(int num : map.keySet()){
           int freq = map.get(num);
           if(!freqMap.containsKey(freq)){
               freqMap.put(freq, new LinkedList<>());
           }
           freqMap.get(freq).add(num);
        }

        List<Integer> res = new ArrayList<>();
        while(res.size()<k){
            Map.Entry<Integer, List<Integer>> entry = freqMap.pollLastEntry();
            res.addAll(entry.getValue());
        }
        return res;
    }