Top K Frequent Elements – Java

Runtime O(nlogn)

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> times = new HashMap<Integer, Integer>();
        for(int i=0; i<nums.length; i++) {
            if(times.get(nums[i])!=null) {
                times.put(nums[i], times.get(nums[i])+1);
            } else {
                 times.put(nums[i], 1);
            }
        }
        List<Integer> list = new ArrayList<Integer>(times.keySet());
        list.sort((a,b)->times.get(b)-times.get(a));
        return list.subList(0,k);
    }
}

Optimized

Runtime O(n)

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
       //count the frequency for each element
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
            int max = 0;
    for(int num: nums){
        if(map.containsKey(num)){
            max = Math.max(map.get(num)+1, max);
            map.put(num, map.get(num)+1);
        }else{
            max = Math.max(max, 1);
            map.put(num, 1);
        }
    } 
   
    ArrayList<Integer>[] arr = (ArrayList<Integer>[]) new ArrayList[max+1];
    for(int i=1; i<=max; i++){
        arr[i]=new ArrayList<Integer>();
    }
 
    for(Map.Entry<Integer, Integer> entry: map.entrySet()){
        int count = entry.getValue();
        int number = entry.getKey();
        arr[count].add(number);
    }
 
    List<Integer> result = new ArrayList<Integer>();
 
    for(int j=max; j>=1; j--){
        if(arr[j].size()>0){
            for(int a: arr[j]){
                result.add(a);
                if(result.size()==k){
                    return result;
                }
            }
        }
    }
 
    return result;
    }
}