Counting Sort and Bucket Sort: The Linear-Time Tricks Interviewers Love

Most candidates know that comparison-based sorting cannot beat O(n log n). Fewer remember that when the input has structure, such as small integer ranges or values spread evenly over an interval, you can sort in linear time. Recognizing that structure is a classic way to turn an "acceptable" interview answer into an optimal one. Counting sort If every value is an integer in a known range [0, k), count how many times each value appears, then rebuild the array from the counts. def counting_sort(nums, k): count = [0] * k for x in nums: count[x] += 1 out = [] for v in range(k): out.extend([v] * count[v]) return out Time is O(n + k) and space is O(k). It wins whenever k is not much larger than n. For a stable version (needed when sorting records by key), convert counts into prefix sums and place items from right to left. Bucket sort When values are spread fairly evenly over a range, split the range into n buckets, drop each value into its bucket, sort each small bucket, and concatenate. The expected time is O(n) for uniform input. In interviews, buckets often appear in disguised form rather than as a full sort. Interview problems where this matters 1. Sort Colors (Dutch national flag): only three values, so counting is the simplest correct answer, though interviewers may then ask for the one-pass three-pointer version. 2. Top K Frequent Elements: frequencies are at most n, so create buckets indexed by frequency and read from the highest bucket down. This gives O(n) instead of the O(n log k) heap approach. 3. Sort Characters by Frequency: the same bucket-by-frequency idea on characters. 4. Maximum Gap: find the largest gap between sorted neighbors in linear time. Using n - 1 buckets guarantees the maximum gap lies between buckets, so you only track each bucket's min and max. 5. H-Index: citation counts above n can be capped at n, which makes a counting array of size n + 1 enough. 6. Contains Duplicate III / nearby almost-duplicates: bucket values by width t + 1 so any two numbers within t land in the same or adjacent buckets. How to bring it up in an interview Start with the general solution, usually sorting or a heap, and state its complexity. Then ask a clarifying question about the input: "Are the values bounded?" or "Is the frequency at most n?" If the answer is yes, propose the counting or bucket approach and explain why it is linear. Interviewers value the clarifying question as much as the optimization because it shows you read constraints carefully. Common pitfalls - Using counting sort when k is huge (for example, 32-bit integers). The memory cost becomes the problem. - Forgetting negative numbers: shift values by the minimum first. - Not handling empty buckets in problems like Maximum Gap. - Claiming bucket sort is always O(n). It is expected linear for uniform input, and it can degrade on skewed data. Practice plan Solve Top K Frequent Elements both ways, with a heap and with buckets, and practice explaining the trade-off in under a minute. Then tackle Maximum Gap, which is a favorite "hard" follow-up. Explaining constraints and trade-offs clearly under time pressure is a skill of its own. Linkjob AI (https://linkjob.ai) provides real-time help during job interviews and technical interviews, helping you keep the reasoning structured while you code. It works best alongside deliberate practice. Takeaway: when values are bounded or evenly spread, think counting or buckets before you reach for a comparison sort.