Java: Top K Frequent Elements

Thought Process

To find the Top K frequent elements, we need an efficient approach to count and prioritize frequencies. First, we use a hash map to count frequencies of each element. Then, we use a min heap to dynamically track the K most frequent elements, removing smaller frequencies as we iterate. Finally, we extract the result from the heap. 

class Solution {
    
    public int[] topKFrequent(int[] nums, int k) {
        
        Map<Integer,Integer> mp = new HashMap<>();
        int[] ans = new int[k];
        for(int i = 0; i < nums.length; i++) {

            mp.putIfAbsent(nums[i], 0);
            mp.put(nums[i], mp.get(nums[i]) + 1);
        }
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
        for(Map.Entry<Integer, Integer> entity : mp.entrySet()) {

            int x = entity.getKey();
            int y = entity.getValue();

            pq.offer(new int[]{x, y});

            if(pq.size() > k)
                pq.poll();
        }
        int idx = 0;
        while(!pq.isEmpty()) {
            ans[idx++] = pq.poll()[0];
        }
        return ans;
    }
}

Code Complexity

Time Complexity: O(n log k)

Building the frequency map takes O(n) time, and heap operations take O(n log k) as we maintain at most k elements.

Space Complexity: O(n)

We use extra space for the frequency map and priority queue, both proportional to the input size.

Code copied!