← Back to Index

📚 Top K Frequent Elements – Java Cheat Sheet

📌 What Is It?

The Top K Frequent Elements problem involves finding the K most frequent elements in an array. This is commonly solved using a min-heap or bucket sort depending on the constraints.

🧱 Pattern Template

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        for (int num : nums) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }

        PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>(
            (a, b) -> a.getValue() - b.getValue()
        );

        // Step 1: Add elements to the heap
        for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
            minHeap.offer(entry);
            if (minHeap.size() > k) {
                minHeap.poll(); // Remove the least frequent element
            }
        }

        // Step 2: Extract the top K frequent elements
        int[] result = new int[k];
        int index = 0;
        while (!minHeap.isEmpty()) {
            result[index++] = minHeap.poll().getKey();
        }

        return result;
    }
}

📊 Time Complexity

• Frequency Map Construction: O(N) – Iterating through the array.
• Heap Operations: O(N log K) – Adding and removing elements from the heap.
• Overall Complexity: O(N log K).

✅ Use Cases

• Finding the most frequent elements in a dataset
• Applications in recommendation systems and search engines
• Efficiently processing large datasets

📘 Common LeetCode Problems

• 347. Top K Frequent Elements [Medium] Heap
• 451. Sort Characters By Frequency [Medium] Heap

🧪 Example: Top K Frequent Elements

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Explanation:
- The frequency of 1 is 3, 2 is 2, and 3 is 1.
- The top 2 frequent elements are [1, 2].

▶️ View Animation

💡 Pro Tips

• Use a min-heap to efficiently track the top K frequent elements.
• Edge cases: empty arrays, K greater than the number of unique elements.
• Consider bucket sort for better performance when K is large.