The Quest Begins (The "Why")
I still remember the first time I froze during a technical interview. The interviewer slid a whiteboard marker toward me and said, “Here’s an array of integers where every value is between 0 and 100. Sort it in O(n) time.” My brain instantly went to the trusty Array.prototype.sort() – you know, the one that’s O(n log n) under the hood. I started scribbling a quicksort partition, then realized I was wasting precious minutes on a problem that felt like it should have a shortcut.
After a few awkward silences, the interviewer hinted, “Think about how you’d count votes in an election.” That click felt like finding a hidden lever in a dungeon – suddenly the walls shifted and a linear‑time solution appeared. I walked out of that room buzzing, and ever since I’ve kept counting sort in my back‑pocket for any problem where the data lives in a small, known range.
The Revelation (The Insight)
So why does counting sort work without ever comparing two elements?
Imagine you have a bag of marbles, each painted with a number from 0 to k. Instead of laying them out and comparing each pair, you simply walk through the bag once and tally how many marbles you see of each color. You end up with an array count[0…k] where count[i] tells you exactly how many i‑valued marbles exist.
Now, if you want to output the marbles in sorted order, you just walk through count from 0 to k and emit that many copies of each number. Because we placed the numbers in increasing order of their key, the result is sorted and stable – equal keys appear in the same order they were seen in the original input.
The magic is that we replaced the comparison‑based decision tree (which forces a log n factor) with direct indexing into an auxiliary array. The key itself becomes the address, so we can “jump straight” to the correct bucket. No swapping, no recursion, just a couple of linear scans.
Wielding the Power (Code & Examples)
The Naïve Attempt
function naiveSort(arr) {
return arr.slice().sort((a, b) => a - b); // O(n log n) in V8
}
That works fine for random data, but when the interviewer promises O(n) we’re over‑engineering.
Counting Sort in Action
/**
* Sorts an array of non‑negative integers where each value ≤ maxVal.
* Returns a new sorted array (does not mutate the input).
*/
function countingSort(arr, maxVal) {
const count = new Array(maxVal + 1).fill(0);
const output = new Array(arr.length);
// 1️⃣ Frequency pass
for (const v of arr) {
count[v]++; // O(n)
}
// 2️⃣ Transform to positions (cumulative sum)
for (let i = 1; i <= maxVal; i++) {
count[i] += count[i - 1]; // O(k)
}
// 3️⃣ Place elements (iterate backwards for stability)
for (let i = arr.length - 1; i >= 0; i--) {
const v = arr[i];
output[count[v] - 1] = v;
count[v]--; // O(n)
}
return output;
}
Why it’s O(n + k):
- First loop touches each element once → O(n).
- Second loop runs over the range of possible keys → O(k).
- Third loop again touches each element once → O(n).
If
kis proportional ton(or just a small constant), the whole thing collapses to O(n).
Interview Problem #1 – Sort 0s, 1s, 2s (Dutch National Flag)
LeetCode 75 asks you to sort an array containing only 0, 1, and 2 in‑place. Counting sort gives us a dead‑simple solution, though we can also do it in one pass – the counting version is easier to reason about when you’re nervous.
function sortColors(nums) {
// Since the range is 0…2, maxVal = 2
const sorted = countingSort(nums, 2);
// copy back to satisfy the in‑place requirement
for (let i = 0; i < nums.length; i++) nums[i] = sorted[i];
}
That’s it – three linear passes, no fancy pointer juggling.
Interview Problem #2 – Find the Duplicate Number
LeetCode 287 gives you an array nums of length n + 1 where each integer is in [1, n] and exactly one value appears twice. We can reuse the counting idea without extra space by using the array itself as the frequency table (a common interview twist).
function findDuplicate(nums) {
// First pass: place each number at its "home" index (value-1)
for (let i = 0; i < nums.length; i++) {
const val = Math.abs(nums[i]);
if (nums[val - 1] < 0) return val; // already negative → duplicate
nums[val - 1] = -nums[val - 1]; // mark as seen
}
// (Optional) restore the array if needed
for (let i = 0; i < nums.length; i++) nums[i] = Math.abs(nums[i]);
}
The first loop is O(n); we never allocate another array, achieving O(1) extra space. It’s essentially counting sort where the “count” array is the input itself, using sign bits as markers.
Why This New Power Matters
Counting sort isn’t a universal replacement for quicksort or mergesort – it shines when:
- The key range is limited (think scores 0‑100, ages 0‑120, or categorical IDs).
- Stability is required (e.g., sorting records by secondary key after a primary sort).
- You need guaranteed linear time – no dependence on input distribution, unlike quicksort’s worst case.
When the range balloons (say, sorting 64‑bit integers), the auxiliary array becomes prohibitive and you’d fall back to a comparison‑based method. But for those frequent “small‑range” scenarios – leaderboards, histogram building, radix sort’s inner loop, or even preprocessing for greedy algorithms – counting sort feels like unlocking a secret level in a game.
Think of it like the Sorting Hat in Harry Potter: it doesn’t compare students’ traits by weighing them against each other; it simply looks at each quality and puts the kid straight into the house that matches. One glance, one decision, and the whole choir is ordered.
Your Turn
Try this: given an array of strings where each string is a lower‑case word of length ≤ 10, sort them lexicographically using counting sort on each character position (i.e., a least‑significant‑digit radix sort). Notice how the inner counting sort stays O(n) while the outer loop runs over the fixed word length.
Drop your solution in the comments, or tell me about a time you swapped a O(n log n) sort for a counting‑sort win and felt the interview pressure melt away. Happy coding! 🚀
