Top K Frequent Elements
Understanding the Problem
We have an array of integers that may contain duplicates, and we need to find which elements appear most often. We want the top k by frequency. The order of the output doesn't matter, which gives flexibility in how we collect results.
There are two steps: counting how often each element appears, then selecting the k elements with the highest counts. Counting is straightforward with a hash map. The second step is where the approaches differ, because how we select the top k determines whether the solution is O(n log n), O(n log k), or O(n).
Key Constraints:
1 <= nums.length <= 10^5→ With n up to 100,000, O(n log n) passes, but the follow-up asks us to beat it. This points toward O(n log k) or O(n) solutions.kis valid and the answer is unique → We don't need to handle ties or invalid k values.
Approach 1: Sort by Frequency
Intuition
Count how often each element appears, then sort the unique elements by frequency and take the top k.
A hash map counts frequencies in one pass. We then sort the unique elements by their frequency in descending order. The first k elements in the sorted list are the answer.
Algorithm
- Build a hash map
freqwhere each key is an element fromnumsand the value is its count. - Collect all unique elements (the keys of the map).
- Sort these unique elements by their frequency in descending order.
- Return the first
kelements from the sorted list.
Example Walkthrough
Code
- Time Complexity: O(n log n). Counting frequencies takes O(n). Sorting the unique elements takes O(m log m) where m is the number of unique elements, and in the worst case m = n.
- Space Complexity: O(n). The frequency map stores up to n entries, and the sorted list uses O(m) space.
This sorts all unique elements when we only need the top k. The next approach tracks only k elements at a time, lowering the cost of the selection step.
Approach 2: Min-Heap
Intuition
Instead of sorting all unique elements, maintain a min-heap of size k. The heap holds the k most frequent elements seen so far. When a new element arrives, compare its frequency to the smallest frequency in the heap. If it's larger, evict the minimum and insert the new one.
A min-heap, not a max-heap, is the right choice here. The minimum frequency among the current top k candidates sits at the top of a min-heap, so removing the weakest candidate is an O(log k) operation. Any element still in the heap after processing every unique element has a frequency at least as high as every element that was evicted, so the final heap contents are the k most frequent.
Algorithm
- Build a frequency map from
nums. - Create a min-heap that orders elements by their frequency.
- For each unique element, add it to the heap. If the heap size exceeds k, remove the minimum.
- After processing all unique elements, the heap contains exactly the k most frequent elements.
- Extract all elements from the heap into the result array.
Example Walkthrough
Code
- Time Complexity: O(n log k). Counting frequencies is O(n). For each of the m unique elements, we do a heap operation costing O(log k). Since m <= n, the total is O(n log k).
- Space Complexity: O(n). The frequency map uses O(n) space. The heap uses O(k) space. Total is O(n).
Every unique element still costs a log k heap operation. The final approach removes the logarithmic factor by bucketing elements directly by their frequency.
Approach 3: Bucket Sort
Intuition
The maximum frequency any element can have is n, the length of the array. So we can create an array of buckets where bucket[i] holds all elements that appear exactly i times. Walking from the highest bucket down and collecting elements gives the most frequent ones first.
This eliminates sorting and heap operations. The bucket array has size n+1, placing an element into its bucket is O(1), and walking the buckets from the end visits at most n+1 indices. The whole thing runs in O(n) time.
Algorithm
- Build a frequency map from
nums. - Create an array
bucketsof size n+1, wherebuckets[i]is a list of elements with frequency i. - Place each unique element into its corresponding bucket based on its frequency.
- Iterate from the highest index (n) down to 1. For each non-empty bucket, add its elements to the result.
- Stop once we've collected k elements.
Example Walkthrough
Code
- Time Complexity: O(n). Counting frequencies is O(n). Creating and filling the buckets is O(n). Walking the buckets to collect k elements visits at most n+1 indices. Everything is O(n).
- Space Complexity: O(n). The frequency map uses O(n) space. The bucket array has n+1 slots, and the total elements stored across all buckets is the number of unique elements.