One of my friends recently interviewed at Info Edge,
Interviewer: "Find the k most frequent elements in an array."
Friend: "Sure, I'll use a HashMap to count frequencies, then a min heap of size k to get the top k elements. That's O(n log k) time complexity."
He coded it up cleanly, explained the approach well, and thought he nailed it.
Interviewer: "Good solution. But can you optimize it further? Can you do better than O(n log k)?"
My friend paused. He knew his solution was already optimal... or was it? He couldn't think of anything better. The interviewer smiled and said, "Think about the constraints. What's the maximum frequency an element can have?"
That hint led to bucket sort - a technique most of us skip when learning sorting algorithms. My friend hadn't practiced it, couldn't come up with it in the interview, and that became a gap in an otherwise strong performance.
This experience taught me something important: we often ignore "simple" algorithms like bucket sort, counting sort, and radix sort, thinking they're not important. But they can be the difference between a good solution and an optimal one.
The Problem: Top K Frequent Elements
Problem Statement:
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Example:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]The Standard Solution: Min Heap
Most of us (including my friend) would solve it like this:
public int[] topKFrequent(int[] nums, int k) {
// Step 1: Count frequencies
Map<Integer, Integer> freq = new HashMap<>();
for (int num : nums) {
freq.put(num, freq.getOrDefault(num, 0) + 1);
}
// Step 2: Use min heap of size k
PriorityQueue<Map.Entry<Integer, Integer>> minHeap =
new PriorityQueue<>((a, b) -> a.getValue() - b.getValue());
for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
minHeap.offer(entry);
if (minHeap.size() > k) {
minHeap.poll();
}
}
// Step 3: Extract result
int[] result = new int[k];
for (int i = 0; i < k; i++) {
result[i] = minHeap.poll().getKey();
}
return result;
}Time Complexity: O(n + m log k) where n is array length, m is unique elements
Space Complexity: O(m)
This is a solid solution. It's what most people would code in an interview. But there's a hidden optimization opportunity.
The Hidden Gem: Bucket Sort Approach
Key Insight: The frequency of any element is bounded. An element can appear at most n times (where n is the array length). This means frequencies range from 1 to n.
When we have a bounded range like this, we can use bucket sort to achieve true O(n) time complexity!
The Idea:
- Create buckets indexed by frequency
- Bucket[i] contains all elements that appear exactly i times
- To get top k frequent elements, iterate from highest frequency buckets down
Code:
public int[] topKFrequent(int[] nums, int k) {
// Step 1: Count frequencies - O(n)
Map<Integer, Integer> freq = new HashMap<>();
for (int num : nums) {
freq.put(num, freq.getOrDefault(num, 0) + 1);
}
// Step 2: Create buckets - O(n)
// buckets[i] = list of elements with frequency i
List<Integer>[] buckets = new List[nums.length + 1];
for (int i = 0; i <= nums.length; i++) {
buckets[i] = new ArrayList<>();
}
// Step 3: Put elements in corresponding frequency buckets - O(m)
for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
int frequency = entry.getValue();
int element = entry.getKey();
buckets[frequency].add(element);
}
// Step 4: Collect top k from highest frequency buckets - O(k)
int[] result = new int[k];
int index = 0;
// Start from highest frequency and go down
for (int i = buckets.length - 1; i >= 0 && index < k; i--) {
for (int num : buckets[i]) {
result[index++] = num;
if (index == k) {
return result;
}
}
}
return result;
}Time Complexity: O(n) - True linear time!
Space Complexity: O(n)
Why This Works:
-
Frequencies are bounded: An element can't appear more than n times, so we need at most n+1 buckets.
-
Direct indexing: Instead of sorting or using heaps, we directly place elements in buckets indexed by their frequency. This is O(1) per element.
-
Natural ordering: Buckets are already "sorted" by frequency - higher index = higher frequency.
-
Early termination: We stop as soon as we've collected k elements.
Breaking Down the Bucket Sort Approach
Step-by-Step Visualization:
For nums = [1,1,1,2,2,3], k = 2:
After Step 1 (Frequency Count):
freq = {1: 3, 2: 2, 3: 1}After Step 2-3 (Building Buckets):
buckets[0] = []
buckets[1] = [3] // element 3 appears 1 time
buckets[2] = [2] // element 2 appears 2 times
buckets[3] = [1] // element 1 appears 3 times
buckets[4] = []
buckets[5] = []
buckets[6] = []Step 4 (Collecting Top K):
- Start from buckets[6], empty
- buckets[5], empty
- buckets[4], empty
- buckets[3] has [1], collect it → result = [1]
- buckets[2] has [2], collect it → result = [1, 2]
- We have k=2 elements, done!
Result: [1, 2]
Complete Problem List to Practice
- Top K Frequent Elements
- Sort Characters By Frequency
- Sort Array by Increasing Frequency
- Find All Duplicates in an Array
- Top K Frequent Words
- Reorganize String
- Task Scheduler
- H-Index
- Least Number of Unique Integers after K Removals
- Reduce Array Size to The Half
- Maximum Frequency Stack
- Rearrange String k Distance Apart
Bucket Sort vs Other Non-Comparison Sorts
Counting Sort:
- Works when range is small (like 0-100)
- Counts occurrences of each value
- Reconstructs sorted array from counts
Radix Sort:
- Sorts digit by digit
- Works for numbers or strings
- O(d × n) where d is number of digits
Bucket Sort:
- Distributes elements into buckets
- Each bucket represents a range
- Can handle larger ranges than counting sort
When to use each:
- Counting Sort: Range is very small (0-100), need stable sort
- Radix Sort: Sorting integers or strings with fixed-length keys
- Bucket Sort: Range is bounded (like 1 to n), frequency-based problems
Final Thoughts
Bucket sort isn't flashy. It doesn't involve complex trees or sophisticated algorithms. It's just using the constraint that frequencies are bounded. But that simplicity is its power.
In my friend's case, not knowing this one technique affected his interview performance. He was strong everywhere else, but that gap was visible.
Don't let the same happen to you. Spend a few days learning bucket sort. Solve 10-15 problems using it. Understand when it applies. It's a small investment that can make a big difference.
Remember: Optimal solutions often come from recognizing problem constraints, not just applying the fanciest algorithms.
Related Posts
Check out my posts which may help you in your preparation :
- Complete DP Problems & Resources Guide
- Complete Graph Problems & Resources Guide
- 13 DP Patterns for Interview Preparation
- 10 Dijkstra Variations for Interview Preparation
- Understanding Time Complexity: The 10^8 Operations Rule
- 10 Essential Design Problems for DSA Interviews
- Essential CS Fundamental Topics For Interviews
- Essential Graph Patterns for Coding Interviews
- Essential String Patterns for Coding Interviews
- 15 Essential DSA Patterns for Tech Interviews
- The 10 Variations of Two Pointers for Interview Preparation
Have you encountered bucket sort in interviews? What other "simple" algorithms have you seen optimize seemingly optimal solutions? Share your experiences in the comments!
What topic should I cover in my next post? Drop your suggestions!


