Coding Interview PatternsTop K Frequent Elements
MediumTop K Elements
Top K Frequent Elements
Explanation & Solution
Description
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
It is guaranteed that the answer is unique.
Input:nums = [1, 1, 1, 2, 2, 3], k = 2
0
1
1
1
2
1
3
2
4
2
5
3
Output:[1, 2]
0
1
1
2
Explanation: The element 1 appears 3 times and 2 appears 2 times. These are the two most frequent elements.
Constraints
1 <= nums.length <= 10⁵-10⁴ <= nums[i] <= 10⁴kis in the range[1, the number of unique elements in the array]- It is guaranteed that the answer is unique
Approach
Top K Elements pattern
1. Build a Frequency Map
- Iterate through
numsand count how many times each element appears - Store the counts in a hash map where the key is the element and the value is its frequency
2. Create Frequency Buckets
- Create an array of buckets where the index represents the frequency
- The maximum possible frequency is
nums.length, so we neednums.length + 1buckets - Each bucket holds a list of elements that have that particular frequency
3. Fill the Buckets
- For each entry
(num, freq)in the frequency map, placenumintobuckets[freq] - This groups all elements by how often they appear
4. Collect the Top K Elements
- Traverse the buckets from the highest index (highest frequency) down to 0
- Add elements from each bucket to the result array
- Stop as soon as we have collected
kelements
Key Insight
- The core idea is that bucket sort avoids the O(n log n) cost of sorting or the O(n log k) cost of a heap. By using the frequency as an array index, we can collect the most frequent elements in linear time
Time
O(n)we iterate through `nums` once to build the map, then iterate through the buckets which total at most n entriesSpace
O(n)for the frequency map and the bucket arrayVisualization
Input:
[1, 1, 1, 2, 2, 3], k = 2
—
No animation available
Left (L)Right (R)ConvergedDone
0 steps