Q24: How do you find the Top K Frequent Elements in O(n) time using Bucket Sort?
- Build a character/number frequency map (
map.put(num, count)). - Create an array of lists
List<Integer>[] buckets = new List[nums.length + 1], where array index represents element frequency. - Populate buckets with numbers corresponding to their frequency count.
- Iterate buckets backwards from
nums.lengthdown to 1, collecting elements until $k$ elements are gathered.
Bucket Sort Top K Frequent Elements
import java.util.*;
public class TopKFrequent {
public static int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> countMap = new HashMap<>();
for (int num : nums) countMap.put(num, countMap.getOrDefault(num, 0) + 1);
List<Integer>[] bucket = new List[nums.length + 1];
for (int key : countMap.keySet()) {
int freq = countMap.get(key);
if (bucket[freq] == null) bucket[freq] = new ArrayList<>();
bucket[freq].add(key);
}
int[] result = new int[k];
int index = 0;
for (int pos = bucket.length - 1; pos >= 0 && index < k; pos--) {
if (bucket[pos] != null) {
for (int num : bucket[pos]) {
result[index++] = num;
if (index == k) return result;
}
}
}
return result;
}
}💡 Uses array indices to group elements by occurrence frequency for linear $O(n)$ performance.
Key Takeaways
- Bucket index represents element frequency count.
- Achieves optimal $O(n)$ linear time complexity, bypassing $O(n log n)$ sorting.
Knowledge Check
Why is Bucket Sort able to solve Top K Frequent Elements in O(N) time compared to Min-Heap's O(N log K)?