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: ```java public int[] topKFrequent(int[] nums, int k) { // Step 1: Count frequencies Map freq = new HashMap<>(); for (int num : nums) { freq.put(num, freq.getOrDefault(num, 0) + 1); } // Step 2: Use min heap of size k PriorityQueue> minHeap = new PriorityQueue<>((a, b) -> a.getValue() - b.getValue()); for (Map.Entry 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:** ```java public int[] topKFrequent(int[] nums, int k) { // Step 1: Count frequencies - O(n) Map 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[] 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 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:** 1. **Frequencies are bounded:** An element can't appear more than n times, so we need at most n+1 buckets. 2. **Direct indexing:** Instead of sorting or using heaps, we directly place elements in buckets indexed by their frequency. This is O(1) per element. 3. **Natural ordering:** Buckets are already "sorted" by frequency - higher index = higher frequency. 4. **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 1. [Top K Frequent Elements](https://leetcode.com/problems/top-k-frequent-elements/) 2. [Sort Characters By Frequency](https://leetcode.com/problems/sort-characters-by-frequency/) 3. [Sort Array by Increasing Frequency](https://leetcode.com/problems/sort-array-by-increasing-frequency/) 4. [Find All Duplicates in an Array](https://leetcode.com/problems/find-all-duplicates-in-an-array/) 5. [Top K Frequent Words](https://leetcode.com/problems/top-k-frequent-words/) 6. [Reorganize String](https://leetcode.com/problems/reorganize-string/) 7. [Task Scheduler](https://leetcode.com/problems/task-scheduler/) 8. [H-Index](https://leetcode.com/problems/h-index/) 9. [Least Number of Unique Integers after K Removals](https://leetcode.com/problems/least-number-of-unique-integers-after-k-removals/) 10. [Reduce Array Size to The Half](https://leetcode.com/problems/reduce-array-size-to-the-half/) 11. [Maximum Frequency Stack](https://leetcode.com/problems/maximum-frequency-stack/) 12. [Rearrange String k Distance Apart](https://leetcode.com/problems/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.