Top K Frequent Elements in an Array: Heap and Hash Map Solutions

📌 What is the Top K Frequent Elements Problem?

The Top K Frequent Elements problem asks us to find the k elements that appear most frequently in a given array. This is a common problem in interviews because it tests knowledge of arrays, hash maps, heaps, and sorting.

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

Here, 1 appears 3 times and 2 appears 2 times - the top 2 most frequent elements.

📝 Problem Statement

Given an integer array nums and an integer k, return the k most frequent elements. The solution must be better than O(n log n) in time complexity.

📊 Hash Map + Heap Approach

We use a Hash Map to store the frequency of each number, then use a Heap to keep track of the top k frequent elements.

Steps:

1. Count frequencies: Use a Hash Map to store each element and its frequency.
2. Use a Min Heap: Push each element-frequency pair into a Min Heap (priority queue) of size k.
3. Heap maintenance: If the heap size exceeds k, remove the element with the lowest frequency.
4. Extract results: The heap will now contain k most frequent elements.

public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> freqMap = new HashMap<>();
    for (int num : nums) {
        freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
    }
    PriorityQueue<Map.Entry<Integer, Integer>> minHeap =
        new PriorityQueue<>((a, b) -> a.getValue() - b.getValue());
    for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
        minHeap.add(entry);
        if (minHeap.size() > k) {
            minHeap.poll();
        }
    }
    int[] result = new int[k];
    for (int i = k - 1; i >= 0; i--) {
        result[i] = minHeap.poll().getKey();
    }
    return result;
}

Time Complexity: O(n log k)

Space Complexity: O(n)

⚡ Bucket Sort Approach

We can use bucket sort to achieve O(n) time complexity by grouping elements based on their frequencies.

Steps:

1. Count frequencies: Same as in the heap method.
2. Create buckets: Create a list of lists where the index represents the frequency, and store numbers with that frequency.
3. Collect results: Traverse buckets from highest frequency to lowest until we have k elements.

public int[] topKFrequentBucket(int[] nums, int k) {
    Map<Integer, Integer> freqMap = new HashMap<>();
    for (int num : nums) {
        freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
    }
    List<Integer>[] buckets = new List[nums.length + 1];
    for (int key : freqMap.keySet()) {
        int freq = freqMap.get(key);
        if (buckets[freq] == null) buckets[freq] = new ArrayList<>();
        buckets[freq].add(key);
    }
    List<Integer> resultList = new ArrayList<>();
    for (int i = buckets.length - 1; i >= 0 && resultList.size() < k; i--) {
        if (buckets[i] != null) resultList.addAll(buckets[i]);
    }
    int[] result = new int[k];
    for (int i = 0; i < k; i++) {
        result[i] = resultList.get(i);
    }
    return result;
}

Time Complexity: O(n)
Space Complexity: O(n)

🧠 Why This Problem is Important

• Common interview problem testing heaps and hash maps.
• Improves understanding of frequency counting.
• Teaches efficient sorting techniques beyond simple sort functions.

✅ Conclusion

The Top K Frequent Elements problem demonstrates the importance of selecting the right data structure for performance. Using a heap ensures you can maintain only the top k elements efficiently, while bucket sort pushes efficiency even further. Mastering both methods prepares you for a range of real-world problems involving frequency analysis, search optimization, and data ranking.