#347
Top K Frequent Elements
Medium Bucket sort by frequency
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the k most frequent values in the array (the answer is unique).
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the k values that appear most.
Why this works: count, then bucket values by count (counts are ≤ n) and read buckets from the top.
Example: [1, 1, 1, 2, 2, 3], k = 2
counts 1→3, 2→2, 3→1buckets: 3:[1], 2:[2] → [1, 2]
✦Hints open one at a time
Count frequencies with a HashMap.
A min-heap of size k on frequency gives O(n log k).
Frequencies are between 1 and n, so buckets indexed by frequency give O(n).
↗Approach
Count, then put each value in bucket[freq]. Walk buckets from n down and collect values until you have k.
</>Solution (Java)
import java.util.*;
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> freq = new HashMap<>();
for (int x : nums) freq.merge(x, 1, Integer::sum);
List<List<Integer>> buckets = new ArrayList<>();
for (int i = 0; i <= nums.length; i++) buckets.add(new ArrayList<>());
for (Map.Entry<Integer, Integer> e : freq.entrySet()) buckets.get(e.getValue()).add(e.getKey());
int[] res = new int[k];
int idx = 0;
for (int f = nums.length; f > 0 && idx < k; f--) { // most frequent first
for (int v : buckets.get(f)) {
if (idx < k) res[idx++] = v;
}
}
return res;
}
}!Common mistake
Sorting all map entries by frequency — O(n log n), fine but not the best.
Complexity
- Time: O(n).
- Space: O(n).
Topic: Heaps & Priority Queue
🎬 Episodes 64–68: video coming soon