Posts Top K Frequent Elements
Post
Cancel

Top K Frequent Elements

This question is part of NeetCode150 series.

Problem Description

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

Solution

APPROACH 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {

    public int[] topKFrequent(int[] nums, int k) {

        Map<Integer, Integer> map = new HashMap<>();

        int max = 0;

        for(int i=0; i<nums.length; i++){

            int x = nums[i];

            if(map.containsKey(x)){
                map.put(x, map.get(x) + 1);
            }else{
                map.put(x, 1);
            }

            max = Math.max(max, map.get(x));

        }

        Map<Integer, List<Integer>> m2 = new HashMap<>();

        for(Map.Entry<Integer, Integer> entry: map.entrySet()){

            int key = entry.getKey();
            int value = entry.getValue();

            if(!m2.containsKey(value)){
                List<Integer> l = new ArrayList<>();
                l.add(key);
                m2.put(value, l);
            }else{
                m2.get(value).add(key);
            }

        }


        int[] ans = new int[k];
        int idx=0;

        while(k>0){
            if(m2.containsKey(max)){
                List<Integer> temp = m2.get(max);
                for(Integer x: temp){
                    ans[idx] = x;
                    idx++;
                    k--;
                }
            }
            max--;
        }

        return ans;

    }

}

APPROACH 2 - USING HEAP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {

    public int[] topKFrequent(int[] nums, int k) {

        int n = nums.length;

        // frequency map
        Map<Integer, Integer> map = new HashMap<>();
        for(int i=0; i<n; i++){
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }

        // min heap
        // based on frequency of the elements, which we can get from the hashmap
        Queue<Integer> heap = new PriorityQueue<>( (a, b) -> map.get(a) - map.get(b) );

        // add the keys one by one to the min heap
        // the key with min freq will be at the top after each addition
        // if the size of heap is > k, remove the top most element (keep doing that to have at most k elements in the heap)
        // at the end, we will have k elements in the heap which have the highest freq
        for(Integer x: map.keySet()){
            heap.add(x);
            if(heap.size() > k) heap.poll();
        }

        // get k values from the heap and store it in the result array
        int[] res = new int[k];
        for(int i=0; i<k; i++){
            res[i] = heap.poll();
        }

        return res;

    }

}

This can be solved using max heap also, but we will need to store all n elements in the heap first. So the space complexity will be higher. Using min heap, we can maintain the maximum heap size as k elements, which helps in optimizing the space.

This post is licensed under CC BY 4.0 by the author.