Top K Frequent Elements: HashMap and PriorityQueue Approach

1. Understanding the Problem

The problem statement is as follows:

Given a non-empty array of integers nums and an integer k, return the k most frequent elements.

Let's look at a quick example to make this concrete.

In an interview, good clarifying questions would be:

• What should I do in case of a tie in frequencies? (The problem on platforms like LeetCode often guarantees a unique answer).
• Can k be larger than the number of unique elements?
• What is the range of values in the array?

For today, we'll assume the answer set is unique.

2. The Two-Step Strategy

The most effective way to solve this problem is to break it into two distinct steps:

1. Count Frequencies: First, determine how many times each number appears in the input array.
2. Find the Top K: From the frequency counts, identify the k numbers with the highest frequencies.

Let's tackle each step.

Step 1: Counting Frequencies with a HashMap

This first step should feel familiar after our last lesson. A HashMap<Integer, Integer> is the perfect tool to store each number and its corresponding frequency.

We can iterate through the input array nums and populate our map. For each number, we either initialize its count to 1 or increment its existing count.

// nums = [1, 1, 1, 2, 2, 3], k = 2

Map<Integer, Integer> frequencyMap = new HashMap<>();
for (int num : nums) {
    frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
}

// After the loop, frequencyMap will be:
// {1=3, 2=2, 3=1}

This step takes O(N) time, where N is the number of elements in the input array, and O(M) space, where M is the number of unique elements.

Step 2: Finding the Top K Elements with a PriorityQueue

Now we have our frequencies. The challenge is to find the top k from this map efficiently.

A naive approach would be to dump the map's entries into a list and sort it by frequency. This would work, but sorting takes O(M log M) time. Interviewers will often ask for a solution better than O(M log M).

This is where a heap comes in. A heap is a specialized tree-based data structure ideal for "Top K" problems. In Java, we use the PriorityQueue class, which is implemented as a heap.

To understand the core pattern, the following video gives an excellent high-level overview.

The Min-Heap Trick

As the video explained, the most efficient way to solve this is using a min-heap of size k. Here’s why this seemingly counter-intuitive choice works so well:

• The heap will store the k most frequent elements seen so far.
• Because it's a min-heap, the element at the top (the root) is the one with the lowest frequency among those k elements.
• When we process a new element from our frequency map, we compare its frequency to the root of the heap.
  • If the new element's frequency is greater than the root's, it means the new element deserves to be in the top k. We remove the root (the current "weakest" of the top k) and add the new element.
  • If the new element's frequency is less than or equal to the root's, we do nothing. It doesn't belong in the top k.

This way, the heap acts as a gatekeeper, always maintaining the k elements with the highest frequencies seen so far, and each check/update operation is a fast O(log k).

For a detailed walkthrough, the following text provides a great step-by-step guide.

3. Java Implementation

Now, let's put all the pieces together in a clean, interview-ready Java implementation.

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // Step 1: Build a frequency map. O(N) time.
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        for (int num : nums) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }

        // Step 2: Use a min-heap to find the top k frequent elements.
        // The PriorityQueue will store Map.Entry objects.
        // We use a lambda expression to define the comparator, so the heap is ordered
        // by the frequency (the entry's value). This makes it a min-heap.
        PriorityQueue<Map.Entry<Integer, Integer>> minHeap = 
            new PriorityQueue<>((a, b) -> a.getValue() - b.getValue());
            // An equivalent way is: new PriorityQueue<>(Comparator.comparingInt(Map.Entry::getValue));

        // Iterate through the frequency map. O(M log k) time, where M is unique elements.
        for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
            minHeap.add(entry);
            // If the heap size exceeds k, remove the element with the smallest frequency.
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }

        // Step 3: Extract the results from the heap. O(k log k) time.
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            // The problem statement says the order of the result doesn't matter.
            result[i] = minHeap.poll().getKey();
        }

        return result;
    }
}

Complexity Analysis:

• Time Complexity: O(N log k).
  • Building the HashMap takes O(N).
  • Iterating through the M unique elements and performing heap operations takes O(M log k).
  • Since M <= N, the dominant term is O(N log k). This is better than the O(N log N) sorting approach.
• Space Complexity: O(M + k).
  • O(M) for the HashMap to store M unique elements.
  • O(k) for the PriorityQueue.

4. Interview Discussion: Going Further

In a senior-level interview, after presenting this optimal solution, a great candidate will be prepared to discuss alternatives and trade-offs.

A key follow-up you might encounter is about an even faster solution. While O(N log k) is excellent, there is a way to solve this in O(N) linear time.

This method is a variation of Bucket Sort.

1. Count frequencies with a HashMap as before (O(N)).
2. Create an array of lists (the "buckets"), where the index of the array represents a frequency. buckets[i] will hold a list of all numbers that appeared i times. The size of this array would be nums.length + 1.
3. Iterate through your frequency map and place each number into the correct bucket based on its frequency (O(M)).
4. Iterate backwards from the end of the buckets array (highest frequency) and collect numbers until you have k elements (O(N) in the worst case).

This gives a total time complexity of O(N). The trade-off is space: the buckets array requires O(N) space, which might be more than the HashMap + PriorityQueue approach if the number of unique elements is low. Mentioning this demonstrates a deep command of algorithms.

Conclusion

You've now added another essential problem-solving pattern to your interview toolkit. You've seen how to combine two fundamental data structures, HashMap and PriorityQueue, to create an efficient and elegant solution.

Key Takeaways:

• The 'Top K' family of problems can often be broken down into counting and selecting.
• A HashMap is the standard tool for efficient frequency counting.
• A min-heap of size k is the optimal data structure for finding the top k largest items from a stream or collection, offering an O(N log k) time complexity.
• For interviews, be prepared to discuss the brute-force (sorting) approach, the optimal heap-based solution, and even linear-time alternatives like Bucket Sort, explaining the time/space trade-offs of each.

In our next lesson, we will pivot from problem-solving to a deep dive into the internal workings and performance characteristics of two fundamental collection types: ArrayList and LinkedList. Understanding these trade-offs is crucial for writing high-performance Java code.