5. Top K Frequent Elements

Description

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

Approach 1

• So first create a frequency map with input integer as key and their frequency as value
• Now we will create an array whose elements are List<Integer> the purpose being frequency as key and the elements with that frequency stored as a List
• The size would be input array length as the most frequency someone can have is that
• So now we just iterate through this array in reverse and return k elements

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> freq = new HashMap<>();
        List<Integer>[] bucket = new ArrayList[nums.length + 1];
 
        for (int num: nums) {
            freq.put(num, freq.getOrDefault(num,0) + 1);
        }
 
        for (int key: freq.keySet()) {
            int count = freq.get(key);
            if(bucket[count] == null) {
                bucket[count] = new ArrayList<>();
            }
            bucket[count].add(key);
        }
 
        int index = 0;
        int[] res = new int[k];
        for(int i = nums.length; i >= 0; i--) {
            if(bucket[i] != null) {
                for(int val: bucket[i]) {
                    res[index++] = val;
                    if(index == k) {
                        return res;
                    }
                }
            }
        }
 
        return res;
    }
}