[Leetcode] 347. Top K Frequent Elements

https://leetcode.com/problems/top-k-frequent-elements/description/

initial

isnt this just using hashamp and sorting the value to get top k values

yes but a bit tricky part is when we sort the value, how do we get the key as well cuz that is the answer? Well we can store map.entry inside a list and sort in ascending order on entry's value.

but therer is a bucket sort way with n time

sol

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int num:nums){
            map.put(num,map.getOrDefault(num,0)+1);
        }
        List<Map.Entry<Integer,Integer>> lst = new ArrayList<>();
        for(Map.Entry<Integer,Integer> entry:map.entrySet()){
            lst.add(entry);
        }
        Collections.sort(lst, (a,b)->b.getValue()-a.getValue());
        int[] ans = new int[k];
        for(int i=0; i<k;i++){
            ans[i]=lst.get(i).getKey();
        }
        return ans;
    }
}

sol heap way

u can also use heap

a[0] - b[0] tells Java to sort these arrays in ascending order based on the frequency.

Result: This creates a Min-Heap. The element with the lowest frequency will always be at the top (pq.peek()). we should be creating min heap, not max heap

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

        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
            heap.offer(new int[]{entry.getValue(), entry.getKey()});
            if (heap.size() > k) {
                heap.poll();
            }
        }

        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = heap.poll()[1];
        }
        return res;
    }
}

bucket sort n time

List[] is an array of lists. like in an array, the elements stored are lists. This bucket has n+1 cuz theoretically if its all sam integers, u can have n amount of freq. Also the bucket[i] will store all the numbers that appear i times.

freq = {1=3, 2=2, 3=1}

bucket[1] = [3]   // numbers appearing once
bucket[2] = [2]   // numbers appearing twice
bucket[3] = [1]   // numbers appearing three times
bucket[4..6] = [] // empty

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        // freq map
        Map<Integer, Integer> freq = new HashMap<Integer, Integer>();
        for (int n : nums) {
            freq.put(n, freq.getOrDefault(n, 0) + 1);
        }
        // bucket sort on freq
        List<Integer>[] bucket = new List[nums.length + 1];
        for (int i = 0; i < bucket.length; i++) bucket[i] = new ArrayList();
        for (int key : freq.keySet()) {
            bucket[freq.get(key)].add(key);
        }
        // gather result
        List<Integer> res = new ArrayList();
        for (int i = bucket.length - 1; i >= 0; i--) {
            res.addAll(bucket[i]);
            if (res.size() >= k) break;
        }
        return res;
    }
}

complexity

n log n time
n space

but bucket sort is n time n space