Top K Frequent Elements - Solution & Explanation

Problem Overview: You receive an integer array and an integer k. The task is to return the k most frequent elements in the array. Order does not matter, but the algorithm must be efficient since the input size can be large.

Frequency problems usually start with counting occurrences. The main challenge is extracting the top k elements efficiently without sorting the entire dataset. Two common strategies are a heap-based approach and bucket sort.

Approach 1: Hash Map + Min-Heap (O(n log k) time, O(n) space)

First count how many times each number appears using a hash table. This converts the original array problem into a frequency lookup like {number -> count}. Next, maintain a min-heap of size k using a priority queue. Iterate through the frequency map and push (frequency, value) pairs into the heap. Whenever the heap size exceeds k, remove the smallest frequency element. This keeps only the top k frequent elements in the heap. The complexity is O(n log k) because each heap insertion or removal costs log k, and you perform it for up to n unique elements.

Approach 2: Bucket Sort (O(n) time, O(n) space)

Bucket sort removes the need for a heap entirely. Start by counting frequencies using a hash map. The maximum frequency of any number cannot exceed n, so create an array of buckets where the index represents frequency. Each bucket stores the numbers that appear that many times. After building the buckets, iterate from the highest frequency bucket downwards and collect numbers until you gather k elements. This works because frequencies map directly to indices. The approach runs in O(n) time since both counting and bucket traversal are linear.

Approach 3: Quickselect on Frequencies (Average O(n) time, O(n) space)

Another strategy is applying Quickselect, similar to finding the kth largest element. Build a frequency map, convert it into a list of pairs, and partition the list based on frequency. Each partition step moves higher-frequency elements toward the front until the top k region is identified. Average complexity is O(n), though worst-case becomes O(n²). This approach avoids extra structures like heaps or buckets but is more complex to implement correctly.

Recommended for interviews: The hash map + heap solution is the most commonly expected approach. It demonstrates clear understanding of counting with a array traversal and efficient top-k extraction using a priority queue. Bucket sort is even faster at O(n), and strong candidates often mention it as the optimal solution when frequency bounds allow it.