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.

Solution:

public class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int n : nums){
            Integer val = map.get(n);
            map.put(n, val==null ? 1 : val+1);
        }
        /* frequency starts from 1, so don't forget +1 */
        List<Integer>[] buckets = new List[nums.length+1];
        for(Map.Entry<Integer, Integer> e : map.entrySet()){
            int frq = e.getValue();
            if(buckets[frq]==null) buckets[frq] = new ArrayList<>();
            buckets[frq].add(e.getKey());
        }
        List<Integer> ans = new ArrayList<>();
        for(int i=nums.length-1; i>=0 && ans.size()<k; i--){
            if(buckets[i]!=null) ans.addAll(buckets[i]);
        }
        while(ans.size()>k) ans.remove(ans.size()-1);
        return ans;
    }
}