Top K Frequent Elements
MediumBucket by frequency, read from the top
Count how often each value appears, then pick the k that appear most.
The idea
Count frequencies, then place each value into a bucket indexed by its count. Walking buckets from high to low yields the k most frequent without a full sort.
1
1
1
2
2
3
0
1
2
3
4
5
Step 1 of 8. Find the 2 most frequent values. First count, then bucket by count. Values: 1, 1, 1, 2, 2, 3.
1/8
Optimal
timeO(n)spaceO(n)
Index buckets by frequency.
1const freq = tally(nums);2const buckets = Array.from({length: n + 1}, () => []);3for (const [v, f] of freq) buckets[f].push(v);4const out = [];5for (let f = n; f >= 1 && out.length < k; f--)6 out.push(...buckets[f]);7return out.slice(0, k);Input
- array
- [1, 1, 1, 2, 2, 3]
Memory
- #1
- —
- #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.