My Friend's Info Edge Interview (Bucket Sort Surprise)

838

Google Amazon LeetCode Placement Career DSA Interview

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

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.

Check out my posts which may help you in your 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!

Comments (3)