Top K Frequent Elements

Problem Information

Solution

Semi optimal solution

You can also use a min heap to sort the elements in nums by frequency and only keep the k most frequent.

Optimal Solution

Because we know that the integers in nums are equal or less than the size of nums (which is no more than 100,000). We can use bucket sort to sort by frequency of the elements in nums in O(n).

  • Time Complexity: O(n).
  • Space Complexity: O(n).
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> count = new HashMap<>();
        for (int num: nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }

        int maxFrequency = 10000;
        ArrayList<Integer>[] frequency = new ArrayList[maxFrequency];
        for (int i = 0; i < frequency.length; i++) {
            frequency[i] = new ArrayList<Integer>();
        }

        Set<Integer> keys = count.keySet();

        for (int key: keys) {
            int frequencyOfKey = count.get(key);

            frequency[frequencyOfKey].add(key);
        }

        int[] kElements = new int[k];
        int kElementsIndex = 0;
        for (int i = maxFrequency - 1; i >= 0 && kElementsIndex < k; i--) {
            for (int num : frequency[i]) {
                kElements[kElementsIndex++] = num;

                if (kElementsIndex == k) {
                    return kElements;
                }
            }
        }

        return kElements;
    }
}