Top K Frequent Elements
MediumCount, then bucket by frequency
Problem
Return the k most frequent elements in an array.
Count each value, then use a heap to pull off the k with the highest counts.
The idea
Build a frequency map, then either keep a size-k min-heap for O(n log k), or bucket the values by frequency into an array indexed by count and read it from the top for O(n). A frequency cannot exceed n, which is what makes bucketing possible.
The trick
- Bucket sort gives O(n) because counts are bounded by n.
- The heap version is O(n log k) and simpler to write.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — nums=[1,1,1,2,2,3], k=2 Values: 1, 1, 1, 2, 2, 3.
1freq = counts(nums)2bucket by frequency (index = count)3read buckets from high count until k collectedInput
- array
- [1, 1, 1, 2, 2, 3]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [1, 1, 1, 2, 2, 3], k = 2
- Output:
- [1, 2]
- Explanation:
- 1 (x3) and 2 (x2) are most frequent.
Example 2
- Input:
- nums = [1], k = 1
- Output:
- [1]
- Explanation:
- One value, top-1 is itself.
Example 3
- Input:
- nums = [4, 4, 5, 5, 6], k = 2
- Output:
- [4, 5]
- Explanation:
- 4 and 5 tie for the top two.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.