Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.

For example,
Given[1,1,1,2,2,3]and k = 2, return[1,2].

Note: 
You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

Three Ways

Priority Queue time: O(klogn) space O(n)

TreeMap : time: O(klogn) space O(n)

Bucket Sort : time O(n) space O(n)

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer>[] bucket = new List[nums.length + 1];
        List<Integer> ans = new ArrayList<>();
        if (nums == null|| nums.length ==0) {
            return ans;
        }
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (freqMap.containsKey(nums[i])) {
                freqMap.put(nums[i], freqMap.get(nums[i]) + 1);
            }else{
                freqMap.put(nums[i], 1);
            }
        }
        for (int key : freqMap.keySet()) {
            int freq = freqMap.get(key);
            if (bucket[freq] == null) {
                bucket[freq] = new ArrayList<Integer>();
            }
            bucket[freq].add(key);
        }
        for(int i = bucket.length - 1; i >= 0 && ans.size() < k; i--) {
            if (bucket[i] != null) {
                ans.addAll(bucket[i]);
            }
        }
        return ans;
    } 
}