Top K Frequent Elements - Java Algorithm Solution

The top K frequent elements problem requires identifying the most frequently occurring elements in an array, which can be solved efficiently using various approaches including min-heaps, hash maps, and bucket sorting techniques.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. Can the input array be mutated, or do we need to preserve the original?
2. What is the expected return format — array of elements, list of pairs, or just the frequencies?
3. Are duplicate values in the input allowed, and should they be treated as separate elements?
4. What is the expected size of the input array — small, medium, large?
5. Is there a specific time complexity target for the follow-up (e.g., O(n) vs O(n log k))?

Restate the pattern or problem type in your own words: The Top K Frequent Elements problem asks us to identify the k most frequently occurring elements from a given array. This is a classic ranking problem where we need to process frequency counts and select the top k elements based on their occurrence count.

Clarify the signal words and constraint shape that point to it:

• "Top K" or "K most frequent" signals we're looking for ranking/ordering
• "Frequent elements" suggests we need to count occurrences and rank by frequency
• The constraint of returning only k elements (not all) indicates we should avoid full sorting
• Input size constraints often suggest the need for an efficient O(n) or O(n log k) solution

Note any assumptions you are making:

• The input array can contain negative numbers, zero, and positive numbers
• We're looking for the k most frequent elements (not necessarily unique frequencies)
• The solution should return elements, not their counts
• k is always valid (0 ≤ k ≤ number of unique elements)

Identify whether the pattern is best suited for static, streaming, or online scenarios if relevant: This pattern is primarily designed for static input scenarios where we have complete data upfront. For streaming data, we'd likely need a sliding window or reservoir sampling approach, which would be a different pattern entirely. This is a batch processing problem where we can analyze all elements at once to compute frequencies and rank them accordingly.

2. When to Use This Pattern

Signal words and constraint shapes:

• "Top K" or "K most frequent" in problem description
• "Find the k elements that appear most often"
• "Return the k elements with highest frequency"
• Input size constraints (typically 1 ≤ k ≤ array length)
• Frequency-based ranking criteria

Why this pattern fits better than alternatives: This pattern is specifically designed for frequency-based ranking problems where we need to identify elements with highest occurrence counts. Compared to sorting the entire array (O(n log n)) or using nested loops (O(n²)), this approach leverages specialized data structures to achieve optimal performance. The key insight is that we don't need to sort all elements by frequency - we only care about the top K elements, which allows us to use a min-heap or bucketing approach.

Variations and related patterns:

• When K = 1, this becomes a "most frequent element" problem that can be solved with a simple HashMap
• When K = array length, we want all elements sorted by frequency (can use bucket sort)
• For streaming data with bounded window size, we'd apply a sliding window + frequency tracking approach
• When frequencies are not integers but continuous values, we'd need a different ranking mechanism

Core insight: The key insight is that we can avoid full sorting by maintaining only the top K elements in a data structure that allows efficient insertion and removal of elements based on their frequency rank. This is particularly powerful when K << N, where we can achieve O(n log k) instead of O(n log n) time complexity.

The pattern works best when:

1. We have a well-defined ranking criteria (frequency)
2. The input size is large enough that full sorting would be inefficient
3. We only care about a small subset (K) of the most frequent elements
4. The problem allows for returning results in any order within the top K set

3. Approach Evolution

Interview communication script:

My first instinct is to use a brute force approach where I count frequencies for all elements and then sort them by frequency - that would work but would be O(n²) in the worst case because for each element I'd need to scan the entire array to count occurrences, and then sorting would add another O(n log n). Let me think about how to optimize this...

Actually, I can do better by using a hash map to count frequencies in one pass - that's O(n) time. But I still need to get the top K elements, so I have to sort or find the maximums.

I notice that if I maintain a min-heap of size K, I can keep only the top K frequent elements at any time. When I encounter a new element with higher frequency than the minimum in my heap, I can evict that minimum and add the new element. This way I'm always maintaining exactly K elements in my heap, and the root of the heap will be the minimum frequency among the top K elements.

This approach reduces the time complexity from O(n log n) to O(n log K), which is better when K << n. The key insight is that I don't need to sort all elements - I just need the top K.

Let me think about this more carefully. The heap approach works because:

1. I process each element once to count frequencies - O(n) time
2. For each unique element, I do at most one heap operation - O(log K)
3. Total time is O(n log K)
4. Space is O(K + U) where U is the number of unique elements

This is optimal for the case where K is small compared to n, and it's more efficient than sorting all elements.

Brute-force approach: Count frequency of each element using a hash map, then sort all elements by frequency in descending order and return the first K elements. Time: O(n log n), Space: O(n)

Improved approach: Use a min-heap of size K to maintain only the top K frequent elements. For each unique element, if its frequency is higher than the minimum in the heap, replace that minimum with the current element. Time: O(n log K), Space: O(K + U)

Final approach: Process input once to build frequency map, then use min-heap of size K to keep track of top K frequent elements. When heap size exceeds K, remove the element with minimum frequency. Time complexity O(n log K), Space O(K + U) where U is unique elements.

Key invariants:

• The min-heap always contains at most K elements
• The root of the heap is the minimum frequency among top K elements
• All elements in the heap have frequency ≥ root's frequency
• The final heap contains exactly the top K frequent elements

4. Data Structure Choice

For the Top K frequent elements problem, I'll use a combination of data structures to achieve optimal performance:

Primary Data Structures:

1. HashMap<Integer, Integer> - Used to count frequency of each element

   • Time: O(1) average for insertions and lookups
   • Space: O(n) where n is the number of unique elements
   • Why needed: Essential for tracking how many times each element appears

2. Min-Heap (PriorityQueue) - Maintains top K elements by frequency

   • Time: O(log k) for insertions and removals where k is the target size
   • Space: O(k) for storing at most k elements
   • Why needed: Efficiently keeps track of the smallest frequency among top K elements, allowing easy eviction when we find a more frequent element

Why This Combination Works: The HashMap provides O(1) frequency lookups, while the Min-Heap maintains our result set in sorted order by frequency. This combination allows us to process elements in O(n) time and return top K elements efficiently.

Helper Structure:

• ArrayList - For final result collection
  • Time: O(k) for building the result list
  • Space: O(k) for storing the answer
  • Why needed: Simple container to return the final k elements

This approach avoids storing all n elements in memory while maintaining optimal time complexity for finding top K frequent elements. The heap ensures we never store more than k elements, making space complexity O(k) rather than O(n).

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to show how it works step-by-step.

Example: nums = [1,1,1,2,2,3], k = 2

Step 1: Build frequency map

• Process each element and count occurrences
• 1 appears 3 times, 2 appears 2 times, 3 appears 1 time
• Frequency map: {1: 3, 2: 2, 3: 1}

Step 2: Use min-heap to maintain top k elements

• Process each key-value pair from frequency map
• Add (1,3) to heap → heap: [(1,3)]
• Add (2,2) to heap → heap: [(2,2), (1,3)]
• Add (3,1) to heap → heap size = 3 > k=2, so remove smallest element
• Remove (2,2) → heap: [(1,3), (3,1)]

Step 3: Extract results

• Extract elements from heap to get top k frequent items
• Final result: [1, 3] (or [3, 1] since order doesn't matter)

Edge case handling:

• When k = 0, return empty list
• When input has fewer than k distinct elements, return all elements
• When multiple elements have same frequency, heap maintains proper ordering

The algorithm terminates correctly because:

1. We process all elements once to build frequency map (O(n))
2. We maintain a min-heap of size at most k, so each insertion/removal is O(log k)
3. Final extraction gives us exactly k elements with highest frequencies
4. The min-heap property ensures we always keep the top k frequent items

6. Java Solution

import java.util.*;

public class TopKFrequentElements {
    
    public List<Integer> topKFrequent(int[] nums, int k) {
        // Step 1: Count frequency of each element
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : nums) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }
        
        // Step 2: Use min-heap of size k to keep track of top k elements
        // Heap stores {element, frequency} pairs
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        
        for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
            int element = entry.getKey();
            int frequency = entry.getValue();
            
            if (minHeap.size() < k) {
                minHeap.offer(new int[]{element, frequency});
            } else if (frequency > minHeap.peek()[1]) {
                minHeap.poll();
                minHeap.offer(new int[]{element, frequency});
            }
        }
        
        // Step 3: Extract elements from heap
        List<Integer> result = new ArrayList<>();
        while (!minHeap.isEmpty()) {
            result.add(minHeap.poll()[0]);
        }
        
        return result;
    }
}

This solution uses a min-heap of size k to efficiently track the top k frequent elements. We first count all element frequencies, then maintain a heap that always contains the k most frequent elements seen so far. When we find an element with higher frequency than the smallest in our heap, we replace it. Finally, we extract all elements from the heap to form our result list.

The key insight is that we only need to track elements with frequency at least as high as the kth most frequent element, making our heap size bounded by k rather than the total number of unique elements.

7. Complexity Analysis

Time Complexity: O(n log k)

The solution has three main phases:

1. Count frequencies: O(n) - iterate through array once
2. Build min-heap: O(n log k) - for each of the n elements, we may need to heapify up to k elements
3. Extract results: O(k log k) - extract all k elements from the heap

Since k ≤ n, the dominant term is O(n log k). In the worst case where k = n, this becomes O(n log n).

Space Complexity: O(n + k)

• HashMap storage: O(n) - worst case stores all unique elements
• Min-heap storage: O(k) - always maintains at most k elements
• Result list: O(k) - stores the final k elements

The total space complexity is O(n + k), which simplifies to O(n) in the worst case.

Why these bounds are correct:

The heap-based approach is optimal for this problem because:

• We must examine each element at least once to count frequencies (O(n))
• We need to maintain only the top k elements, which requires a heap of size k
• The heap operations (insert/remove) are O(log k) each, making the overall complexity O(n log k)

This is better than a brute force O(n log n) solution that would sort all elements by frequency, since we only need the top k elements rather than the complete sorted list.

The solution is optimal for the given constraints where k << n, as we avoid sorting the entire frequency distribution.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty array: Handle gracefully with early return or proper initialization
• Single element: Should work correctly without edge case handling
• K = 0: Return empty result set; verify that this is handled in the solution logic

Duplicate Values and Repeated States

• Multiple elements with same frequency: The solution must handle ties properly, typically by returning any valid set of k elements
• All elements appear with same frequency: Solution should return any k elements from the set

Boundary Conditions

• K equals array length: Return all elements in any order
• K exceeds array length: Should not occur per problem constraints but worth considering
• Array with negative numbers: Solution should handle any integer values correctly

Common Implementation Mistakes

• Incorrect use of priority queue ordering: Using PriorityQueue with default ordering instead of custom comparator for frequency-based sorting
• Not handling frequency ties properly: Assuming only one element per frequency level when multiple elements may share same frequency
• Off-by-one errors in result size: Adding one extra element or missing the last element due to incorrect loop bounds
• Mutating input array: Modifying original array when problem constraints prohibit it
• Incorrect frequency counting: Using wrong data structure or logic for counting occurrences

Additional Considerations

• Integer overflow in frequency counting: Though unlikely with typical constraints, should be aware of potential issues
• Null input handling: If input validation is required, ensure null checks are in place
• Performance edge cases: Very large arrays with small K values should still perform efficiently

9. Alternative Approaches

There are several alternative approaches to solving the Top K Frequent Elements problem, each with different trade-offs:

1. Sorting Approach: Sort all elements by frequency in descending order, then return the first K elements. This approach has O(n log n) time complexity due to sorting, which is less efficient than our heap-based solution. However, it's simpler to implement and understand.

2. HashMap + Priority Queue with Custom Comparator: Instead of using a min-heap, we could use a max-heap. But this would require building a heap of size n and then extracting K elements, which is still O(n log n) time complexity. The min-heap approach is more efficient as we only maintain a heap of size K.

3. Quickselect Algorithm: We could use the quickselect algorithm to find the Kth most frequent element and partition the array accordingly. This approach has average O(n) time complexity but worst-case O(n²). It's more complex to implement and requires careful handling of edge cases like duplicate frequencies.

4. Bucket Sort Approach: Create buckets where each bucket represents a frequency level, and place elements into their respective buckets. Then traverse from highest to lowest frequency buckets to collect K elements. This approach has O(n) time complexity but requires additional space proportional to the maximum frequency, which could be up to n.

The chosen solution using min-heap is preferred because it provides a good balance between time complexity O(n log k), space complexity O(k), and implementation simplicity. It's particularly efficient when K is small compared to n, which is a common scenario in practice.

The bucket sort approach is optimal for the specific case where we want to find all elements with frequency greater than or equal to some threshold, but it's not as flexible for the general "top K" problem where K can be any value.

10. Test Cases

import java.util.*;

public class TopKFrequentElements {
    
    public List<Integer> topKFrequent(int[] nums, int k) {
        // Implementation would go here
        return new ArrayList<>();
    }
    
    // Test cases
    public static void main(String[] args) {
        TopKFrequentElements solution = new TopKFrequentElements();
        
        // Test case 1: Basic functionality
        int[] nums1 = {1, 1, 1, 2, 2, 3};
        int k1 = 2;
        // Expected: [1, 2] or [2, 1]
        System.out.println("Test 1: " + solution.topKFrequent(nums1, k1));
        
        // Test case 2: Single element array
        int[] nums2 = {1};
        int k2 = 1;
        // Expected: [1]
        System.out.println("Test 2: " + solution.topKFrequent(nums2, k2));
        
        // Test case 3: All elements same
        int[] nums3 = {1, 1, 1, 1};
        int k3 = 2;
        // Expected: [1]
        System.out.println("Test 3: " + solution.topKFrequent(nums3, k3));
        
        // Test case 4: K equals array length
        int[] nums4 = {1, 2, 3};
        int k4 = 3;
        // Expected: [1, 2, 3] in any order
        System.out.println("Test 4: " + solution.topKFrequent(nums4, k4));
        
        // Test case 5: Negative numbers
        int[] nums5 = {-1, -1, 2, 2, 3, 3, 3};
        int k5 = 2;
        // Expected: [-1, 2] or [2, -1] or [3, -1] or [3, 2]
        System.out.println("Test 5: " + solution.topKFrequent(nums5, k5));
    }
}

Sample Test Cases:

1. Basic functionality: nums = [1,1,1,2,2,3], k = 2 → Expected: [1,2] (order doesn't matter)
2. Single element: nums = [1], k = 1 → Expected: [1]
3. All same elements: nums = [1,1,1,1], k = 2 → Expected: [1]
4. K equals array length: nums = [1,2,3], k = 3 → Expected: [1,2,3] (any order)
5. Negative numbers: nums = [-1,-1,2,2,3,3,3], k = 2 → Expected: [-1,2] or similar

Tricky Cases:

• Duplicate frequencies: When multiple elements have the same frequency, any valid ordering is acceptable
• Empty input: nums = [], k = 0 → Expected: []
• Large numbers: Arrays with large integer values or very high frequency elements

Boundary Cases:

• k = 0: Should return empty list
• k > nums.length: Should handle gracefully (though constraints typically prevent this)
• All elements appear once: nums = [1,2,3,4,5], k = 3 → Any 3 elements valid

11. Final Summary

The core idea is to efficiently identify the K most frequent elements in an array by leveraging a frequency map combined with a min-heap to maintain only the top K elements, achieving optimal time complexity of O(n log k) where n is the array length. This approach works because we only need to track the K most frequent elements rather than sorting all frequencies, making it highly efficient for large datasets where K ≪ n. The solution's strength lies in its balanced trade-off between time efficiency (O(n log k)) and space usage (O(n + k)), making it ideal for production systems where both performance and memory constraints matter.