Loading…

easyArraysSometimes asked

Counting Sort 2

Q: How do you solve Counting Sort 2 using the Count then Expand Buckets (Optimal) approach?

When to use it: The intended solution — describe it as 'count, then walk buckets ascending and re-emit'. Counting Sort 2 finishes what Counting Sort 1 started: it turns the histogram back into a sorted sequence. **Phase 1 — count.** Same as before: `freq[x]++` for every input value, giving a 100-slot histogram in `O(n)`. **Phase 2 — expand.** Walk the buckets from index `0` up to `99`. For each value `v`, append `v` to the output exactly `freq[v]` times. Because we visit buckets in ascending order and emit all copies of a smaller value before any larger value, the concatenation is automatically sorted. **Why this is genuinely a sort.** We never compare two elements. The sorted order is implied entirely by the bucket indices: smaller index = smaller value = emitted earlier. That is how counting sort dodges the `Ω(n log n)` comparison lower bound and runs in linear time when `k` is small. **Why it is stable (and why that matters).** If, instead of regenerating values, you place original records into output positions using a prefix-sum of counts and scan the input from the end, equal keys keep their input order. Stability is irrelevant when sorting bare integers but becomes essential the moment each key carries a payload — which is exactly The Full Counting Sort. Time complexity: O(n + k). Space complexity: O(n + k).

Q: How do you solve Counting Sort 2 using the Stable Placement via Prefix Sums approach?

When to use it: Mention when the interviewer asks for stability or hints that keys will later carry payloads (radix sort, Full Counting Sort). The expand-buckets version regenerates values and so cannot carry payloads. The stable version instead computes, for each key, the index where its block begins, then drops each original element into its slot. **Prefix sum = start positions.** After counting, replace `freq[v]` with the number of elements with key `< v` (a running total). Now `freq[v]` is the first output index for key `v`. **Place from the back for stability.** Iterate the input from the last element to the first. For element with key `v`, write it at `output[--positions[v]]`. Scanning backward while decrementing keeps earlier-input equal keys at earlier output indices — the definition of a stable sort. **Why bother for plain integers?** You usually don't — the expand version is simpler. But the instant keys carry satellite data (strings, records), stability is what makes counting sort correct, and this is the template radix sort applies digit by digit. Time complexity: O(n + k). Space complexity: O(n + k).

Arrays & Hashing · 57 of 83 · 7 min

Given a list of integers in the range 0 to 99, return the list sorted in non-decreasing order using counting sort (no comparison-based sort).

In plain English

Sorting here is not about comparing elements — it is about knowing, for each possible value 0..99, how many copies exist. Walking the buckets from 0 upward and re-emitting each value the right number of times reproduces the sorted list directly.

Examples

Example 1

Input: arr = [1, 1, 3, 2, 1]
Output: [1, 1, 1, 2, 3]
Note: freq = {1:3, 2:1, 3:1}. Walk values ascending: emit 1 three times, 2 once, 3 once.

Example 2

Input: arr = [5, 2, 5, 0]
Output: [0, 2, 5, 5]
Note: freq = {0:1, 2:1, 5:2}. Ascending bucket walk yields 0, 2, 5, 5.

Constraints

100 ≤ n ≤ 10⁶
0 ≤ arr[i] < 100
Output is the input sorted in non-decreasing order

Clarifying questions4First question: Am I allowed to use the language's built-in sort?Explore questions

Q1.Am I allowed to use the language's built-in sort?
No — the exercise is specifically to implement counting sort, which is non-comparison-based.
Q2.What is the value range?
0 to 99 inclusive, so a 100-slot count array covers everything.
Q3.Are duplicates expected?
Yes, frequently — a bucket count can be far greater than 1, and all copies appear consecutively.
Q4.Should the output length equal the input length?
Yes — the bucket counts sum to n, so reconstruction emits exactly n values.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Build the frequency array of size 100 from the input, then walk values 0..99 and append each value `freq[value]` times to the output. That reconstructs the fully sorted list in O(n + k) without a single comparison. The key realisation: once you know how many of each value there are, the sorted order is fully determined.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you understand that a histogram already encodes sorted order, so reconstruction is just an ascending bucket walk — and that this gives a non-comparison O(n + k) sort.

Where candidates slip

Emitting the count instead of the value, or iterating buckets in the wrong (descending) order and producing a reverse-sorted list.

How to stand out

Explain why counting sort can beat Ω(n log n) (it never compares), and note that preserving input order within a bucket makes it stable — the property radix sort relies on.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Count then Expand Buckets (Optimal)Optimal	`O(n + k)`	`O(n + k)`	The intended solution — describe it as 'count, then walk buckets ascending and re-emit'.	Read
2	Stable Placement via Prefix Sums	`O(n + k)`	`O(n + k)`	Mention when the interviewer asks for stability or hints that keys will later carry payloads (radix sort, Full Counting Sort).	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Two phases of counting sort

How to read it:Count, then expand the buckets in ascending order to rebuild the sorted list.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2 · Optimal

Count then Expand Buckets (Optimal)

TimeO(n + k)SpaceO(n + k)

The intended solution — describe it as 'count, then walk buckets ascending and re-emit'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Suppose you already had the frequency array from Counting Sort 1. How would you turn those counts back into a sorted list?

2Hint 2Explore hint

If value 1 occurred 3 times, the sorted output must start with three 1s. Generalise: emit each value as many times as its count.

3Hint 3Explore hint

Walk the buckets from index 0 to 99 in order — that ascending walk is exactly what produces sorted order.

A · Core idea

Counting Sort 2 finishes what Counting Sort 1 started: it turns the histogram back into a sorted sequence.

Phase 1 — count. Same as before: freq[x]++ for every input value, giving a 100-slot histogram in O(n).

Phase 2 — expand. Walk the buckets from index 0 up to 99. For each value v, append v to the output exactly freq[v] times. Because we visit buckets in ascending order and emit all copies of a smaller value before any larger value, the concatenation is automatically sorted.

Why this is genuinely a sort. We never compare two elements. The sorted order is implied entirely by the bucket indices: smaller index = smaller value = emitted earlier. That is how counting sort dodges the Ω(n log n) comparison lower bound and runs in linear time when k is small.

Why it is stable (and why that matters). If, instead of regenerating values, you place original records into output positions using a prefix-sum of counts and scan the input from the end, equal keys keep their input order. Stability is irrelevant when sorting bare integers but becomes essential the moment each key carries a payload — which is exactly The Full Counting Sort.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

arr = [1, 1, 3, 2, 1]

Array state

expand v=1

emit 1 three times

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result[1, 1, 1, 2, 3]

C · Code with teaching comments

solution.javaJava

Count then Expand Buckets (Optimal) — optimal

3 teaching notes

1
public int[] countingSort(int[] arr) {
2
    int[] freq = new int[100];
3
    // Phase 1 — tally each value into its bucket in O(n).
4
    for (int x : arr) {
5
        freq[x]++;
6
    }
7
    int[] result = new int[arr.length];
8
    int idx = 0;
9
    // Phase 2 — visit buckets in ascending value order; this ordering yields sorted
10
    // output.
11
    for (int v = 0; v < 100; v++) {
12
        for (int c = 0; c < freq[v]; c++) {
13
            // Emit the VALUE v (not the count), once per copy recorded in freq[v].
14
            result[idx++] = v;
15
        }
16
    }
17
    return result;
18
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.18 lines

D · Why it works and complexityO(n + k) timeO(n + k) spaceOpen the invariant and proofExplore the proof

A histogram is a sorted list in compressed form. Expanding it ascending decompresses it back into sorted order — no comparisons, just bucket arithmetic. That equivalence (counts ⇔ sorted sequence) is the whole reason counting sort exists.

ComplexityO(n + k) time, O(n + k) space — Counting is O(n); the expansion visits k = 100 buckets and emits a total of n values, so O(n + k) time. Output plus the count array is O(n + k) space.

E · Edge cases and pitfalls5arr = [0, 0, 0] — Only bucket 0 is non-zero → output [0, 0, 0].Explore edge cases

Edge cases handled

arr = [0, 0, 0]Only bucket 0 is non-zero → output [0, 0, 0].
arr = [99, 0]Buckets 0 and 99 each hold 1 → ascending walk gives [0, 99].

Pitfalls

Emitting freq[v] (the count) instead of v (the value).
Walking buckets from 99 down to 0 — produces a reverse-sorted list.
Allocating the output with the wrong length when n differs from 100.

03.2

Approach 2 of 2

Stable Placement via Prefix Sums

TimeO(n + k)SpaceO(n + k)

Mention when the interviewer asks for stability or hints that keys will later carry payloads (radix sort, Full Counting Sort).

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What if each number were really a key attached to a record? Re-emitting the value would lose the attached data.

2Hint 2Explore hint

Turn the counts into starting positions with a prefix sum, then place each element at its key's running position.

3Hint 3Explore hint

Scan the input from the last element to the first so equal keys keep their original relative order — that makes it stable.

A · Core idea

The expand-buckets version regenerates values and so cannot carry payloads. The stable version instead computes, for each key, the index where its block begins, then drops each original element into its slot.

Prefix sum = start positions. After counting, replace freq[v] with the number of elements with key < v (a running total). Now freq[v] is the first output index for key v.

Place from the back for stability. Iterate the input from the last element to the first. For element with key v, write it at output[--positions[v]]. Scanning backward while decrementing keeps earlier-input equal keys at earlier output indices — the definition of a stable sort.

Why bother for plain integers? You usually don't — the expand version is simpler. But the instant keys carry satellite data (strings, records), stability is what makes counting sort correct, and this is the template radix sort applies digit by digit.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

arr = [1, 1, 3, 2, 1]

Array state

prefix sums

start[1]=0, start[2]=3, start[3]=4

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result[1, 1, 1, 2, 3]

C · Code with teaching comments

Reference implementation previewpublic int[] countingSortStable(int[] arr) { int n = arr.length; int[] count = new int[100]; for (int x : arr) { count[x]++;Explore the full code

solution.javaJava

Stable Placement via Prefix Sums — reference

2 teaching notes

1
public int[] countingSortStable(int[] arr) {
2
    int n = arr.length;
3
    int[] count = new int[100];
4
    for (int x : arr) {
5
        count[x]++;
6
    }
7
    int[] start = new int[100];
8
    int running = 0;
9
    for (int v = 0; v < 100; v++) {
10
        // Prefix sum: start[v] is the first output index for key v.
11
        start[v] = running;
12
        running += count[v];
13
    }
14
    int[] result = new int[n];
15
    int[] pos = start.clone();
16
    for (int i = 0; i < n; i++) {
17
        int v = arr[i];
18
        // Place this element at its key's next free slot; forward scan with increasing
19
        // pos preserves input order for equal keys.
20
        result[pos[v]++] = v;
21
    }
22
    return result;
23
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.23 lines

D · Why it works and complexityO(n + k) timeO(n + k) spaceOpen the invariant and proofExplore the proof

Prefix sums convert 'how many of each' into 'where each block starts'. That index arithmetic, plus a back-to-front placement pass, is the canonical stable counting sort — the exact engine behind The Full Counting Sort and each pass of radix sort.

ComplexityO(n + k) time, O(n + k) space — Counting and the prefix-sum pass are O(n + k); placing each element is O(n). Output and counts are O(n + k) space.

E · Edge cases and pitfalls5all equal keys — Single block; elements placed in input order — verifies stability.Explore edge cases

Edge cases handled

all equal keysSingle block; elements placed in input order — verifies stability.
n != 100Output length tracks n, not k; prefix sums still total n.

Pitfalls

Forgetting the prefix sum and overwriting earlier placements.
Mixing up forward vs backward scans when stability direction matters.
Sizing prefix/positions arrays inconsistently with the count array.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int[] countingSort(int[] arr) { int[] freq = new int[100]; for (int x : arr) { freq[x]++; }Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Emitting the count instead of the value

freq[v] is how many copies to emit; the thing emitted is the value v. Emitting freq[v] outputs counts, not sorted values.

Explore the code comparison

Don't write this

for v in range(100):
    result.append(freq[v])

Write this instead

for v in range(100):
    result.extend([v] * freq[v])

Descending bucket walk

Counting sort produces sorted order because buckets are visited from smallest value to largest. Reversing that yields a descending list.

Explore the code comparison

Don't write this

for (int v = 99; v >= 0; v--) {
    for (int c = 0; c < freq[v]; c++) result[idx++] = v;
}

Write this instead

for (int v = 0; v < 100; v++) {
    for (int c = 0; c < freq[v]; c++) result[idx++] = v;
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Counting sort — count then reconstruct by expanding buckets

Code pattern to memorize

freq = [0] * 100
for x in arr: freq[x] += 1
result = []
for v in range(100):
    result += [v] * freq[v]
return result

Rules to remember

1Phase 1 counts (freq[x]++); phase 2 rebuilds by emitting value v exactly freq[v] times in increasing v order.
2Iterate the bucket array in ascending index order — that ascending walk is what produces sorted output.
3Emit the value v, not the count freq[v]; the count only tells you how many copies to emit.
4Total emitted length equals n because the counts sum to n.
5No comparisons — counting sort is linear and stable when implemented with stable placement.

Use this pattern when

Sorting integers from a small, known, bounded range
Many duplicates so bucketing pays off
You need O(n) sorting and can spare O(k) space
Stability matters and keys are small integers

Choose another pattern when

Huge or unbounded value range → O(k) space blows up; use a comparison sort
Floating-point or arbitrary comparable objects → no integer bucket index
You only need counts, not the sorted list → that is Counting Sort 1

Interview takeaway

Counts fully determine sorted order: expanding an ascending histogram regenerates the sorted sequence in linear time — the core trick that makes counting and radix sort beat the comparison lower bound.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternCounting sort. Count occurrences into a bounded bucket array, then either expand ascending (values only) or use prefix sums plus stable placement (keys with payloads). Linear time when the key range k is small; the stable variant is the engine of radix sort.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Counting Sort 1
Just the count phase — build the frequency array only.
The Full Counting Sort
Stable counting sort by key while carrying string payloads.
Maximum Gap
Coming soon
Bucket / radix ideas to sort in linear time and find the largest adjacent gap.

Same pattern

←

Counting Sort 1

Continue · Next problem

Merge Sort: Counting Inversions

easyArraysSometimes asked

Counting Sort 2

Arrays & Hashing · 57 of 83 · 7 min

Given a list of integers in the range 0 to 99, return the list sorted in non-decreasing order using counting sort (no comparison-based sort).

In plain English

Examples

Example 1

Input: arr = [1, 1, 3, 2, 1]
Output: [1, 1, 1, 2, 3]
Note: freq = {1:3, 2:1, 3:1}. Walk values ascending: emit 1 three times, 2 once, 3 once.

Example 2

Input: arr = [5, 2, 5, 0]
Output: [0, 2, 5, 5]
Note: freq = {0:1, 2:1, 5:2}. Ascending bucket walk yields 0, 2, 5, 5.

Constraints

100 ≤ n ≤ 10⁶
0 ≤ arr[i] < 100
Output is the input sorted in non-decreasing order

Clarifying questions4First question: Am I allowed to use the language's built-in sort?Explore questions

Q1.Am I allowed to use the language's built-in sort?
No — the exercise is specifically to implement counting sort, which is non-comparison-based.
Q2.What is the value range?
0 to 99 inclusive, so a 100-slot count array covers everything.
Q3.Are duplicates expected?
Yes, frequently — a bucket count can be far greater than 1, and all copies appear consecutively.
Q4.Should the output length equal the input length?
Yes — the bucket counts sum to n, so reconstruction emits exactly n values.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you understand that a histogram already encodes sorted order, so reconstruction is just an ascending bucket walk — and that this gives a non-comparison O(n + k) sort.

Where candidates slip

Emitting the count instead of the value, or iterating buckets in the wrong (descending) order and producing a reverse-sorted list.

How to stand out

Explain why counting sort can beat Ω(n log n) (it never compares), and note that preserving input order within a bucket makes it stable — the property radix sort relies on.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Count then Expand Buckets (Optimal)Optimal	`O(n + k)`	`O(n + k)`	The intended solution — describe it as 'count, then walk buckets ascending and re-emit'.	Read
2	Stable Placement via Prefix Sums	`O(n + k)`	`O(n + k)`	Mention when the interviewer asks for stability or hints that keys will later carry payloads (radix sort, Full Counting Sort).	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Two phases of counting sort

How to read it:Count, then expand the buckets in ascending order to rebuild the sorted list.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2 · Optimal

Count then Expand Buckets (Optimal)

TimeO(n + k)SpaceO(n + k)

The intended solution — describe it as 'count, then walk buckets ascending and re-emit'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Suppose you already had the frequency array from Counting Sort 1. How would you turn those counts back into a sorted list?

2Hint 2Explore hint

If value 1 occurred 3 times, the sorted output must start with three 1s. Generalise: emit each value as many times as its count.

3Hint 3Explore hint

Walk the buckets from index 0 to 99 in order — that ascending walk is exactly what produces sorted order.

A · Core idea

Counting Sort 2 finishes what Counting Sort 1 started: it turns the histogram back into a sorted sequence.

Phase 1 — count. Same as before: freq[x]++ for every input value, giving a 100-slot histogram in O(n).

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

arr = [1, 1, 3, 2, 1]

Array state

expand v=1

emit 1 three times

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result[1, 1, 1, 2, 3]

C · Code with teaching comments

solution.javaJava

Count then Expand Buckets (Optimal) — optimal

3 teaching notes

1
public int[] countingSort(int[] arr) {
2
    int[] freq = new int[100];
3
    // Phase 1 — tally each value into its bucket in O(n).
4
    for (int x : arr) {
5
        freq[x]++;
6
    }
7
    int[] result = new int[arr.length];
8
    int idx = 0;
9
    // Phase 2 — visit buckets in ascending value order; this ordering yields sorted
10
    // output.
11
    for (int v = 0; v < 100; v++) {
12
        for (int c = 0; c < freq[v]; c++) {
13
            // Emit the VALUE v (not the count), once per copy recorded in freq[v].
14
            result[idx++] = v;
15
        }
16
    }
17
    return result;
18
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.18 lines

D · Why it works and complexityO(n + k) timeO(n + k) spaceOpen the invariant and proofExplore the proof

ComplexityO(n + k) time, O(n + k) space — Counting is O(n); the expansion visits k = 100 buckets and emits a total of n values, so O(n + k) time. Output plus the count array is O(n + k) space.

E · Edge cases and pitfalls5arr = [0, 0, 0] — Only bucket 0 is non-zero → output [0, 0, 0].Explore edge cases

Edge cases handled

arr = [0, 0, 0]Only bucket 0 is non-zero → output [0, 0, 0].
arr = [99, 0]Buckets 0 and 99 each hold 1 → ascending walk gives [0, 99].

Pitfalls

Emitting freq[v] (the count) instead of v (the value).
Walking buckets from 99 down to 0 — produces a reverse-sorted list.
Allocating the output with the wrong length when n differs from 100.

03.2

Approach 2 of 2

Stable Placement via Prefix Sums

TimeO(n + k)SpaceO(n + k)

Mention when the interviewer asks for stability or hints that keys will later carry payloads (radix sort, Full Counting Sort).

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What if each number were really a key attached to a record? Re-emitting the value would lose the attached data.

2Hint 2Explore hint

Turn the counts into starting positions with a prefix sum, then place each element at its key's running position.

3Hint 3Explore hint

Scan the input from the last element to the first so equal keys keep their original relative order — that makes it stable.

A · Core idea

Prefix sum = start positions. After counting, replace freq[v] with the number of elements with key < v (a running total). Now freq[v] is the first output index for key v.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

arr = [1, 1, 3, 2, 1]

Array state

prefix sums

start[1]=0, start[2]=3, start[3]=4

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result[1, 1, 1, 2, 3]

C · Code with teaching comments

Reference implementation previewpublic int[] countingSortStable(int[] arr) { int n = arr.length; int[] count = new int[100]; for (int x : arr) { count[x]++;Explore the full code

solution.javaJava

Stable Placement via Prefix Sums — reference

2 teaching notes

1
public int[] countingSortStable(int[] arr) {
2
    int n = arr.length;
3
    int[] count = new int[100];
4
    for (int x : arr) {
5
        count[x]++;
6
    }
7
    int[] start = new int[100];
8
    int running = 0;
9
    for (int v = 0; v < 100; v++) {
10
        // Prefix sum: start[v] is the first output index for key v.
11
        start[v] = running;
12
        running += count[v];
13
    }
14
    int[] result = new int[n];
15
    int[] pos = start.clone();
16
    for (int i = 0; i < n; i++) {
17
        int v = arr[i];
18
        // Place this element at its key's next free slot; forward scan with increasing
19
        // pos preserves input order for equal keys.
20
        result[pos[v]++] = v;
21
    }
22
    return result;
23
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.23 lines

D · Why it works and complexityO(n + k) timeO(n + k) spaceOpen the invariant and proofExplore the proof

ComplexityO(n + k) time, O(n + k) space — Counting and the prefix-sum pass are O(n + k); placing each element is O(n). Output and counts are O(n + k) space.

E · Edge cases and pitfalls5all equal keys — Single block; elements placed in input order — verifies stability.Explore edge cases

Edge cases handled

all equal keysSingle block; elements placed in input order — verifies stability.
n != 100Output length tracks n, not k; prefix sums still total n.

Pitfalls

Forgetting the prefix sum and overwriting earlier placements.
Mixing up forward vs backward scans when stability direction matters.
Sizing prefix/positions arrays inconsistently with the count array.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int[] countingSort(int[] arr) { int[] freq = new int[100]; for (int x : arr) { freq[x]++; }Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Emitting the count instead of the value

freq[v] is how many copies to emit; the thing emitted is the value v. Emitting freq[v] outputs counts, not sorted values.

Explore the code comparison

Don't write this

for v in range(100):
    result.append(freq[v])

Write this instead

for v in range(100):
    result.extend([v] * freq[v])

Descending bucket walk

Counting sort produces sorted order because buckets are visited from smallest value to largest. Reversing that yields a descending list.

Explore the code comparison

Don't write this

for (int v = 99; v >= 0; v--) {
    for (int c = 0; c < freq[v]; c++) result[idx++] = v;
}

Write this instead

for (int v = 0; v < 100; v++) {
    for (int c = 0; c < freq[v]; c++) result[idx++] = v;
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Counting sort — count then reconstruct by expanding buckets

Code pattern to memorize

freq = [0] * 100
for x in arr: freq[x] += 1
result = []
for v in range(100):
    result += [v] * freq[v]
return result

Rules to remember

1Phase 1 counts (freq[x]++); phase 2 rebuilds by emitting value v exactly freq[v] times in increasing v order.
2Iterate the bucket array in ascending index order — that ascending walk is what produces sorted output.
3Emit the value v, not the count freq[v]; the count only tells you how many copies to emit.
4Total emitted length equals n because the counts sum to n.
5No comparisons — counting sort is linear and stable when implemented with stable placement.

Use this pattern when

Sorting integers from a small, known, bounded range
Many duplicates so bucketing pays off
You need O(n) sorting and can spare O(k) space
Stability matters and keys are small integers

Choose another pattern when

Huge or unbounded value range → O(k) space blows up; use a comparison sort
Floating-point or arbitrary comparable objects → no integer bucket index
You only need counts, not the sorted list → that is Counting Sort 1

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Counting Sort 1
Just the count phase — build the frequency array only.
The Full Counting Sort
Stable counting sort by key while carrying string payloads.
Maximum Gap
Coming soon
Bucket / radix ideas to sort in linear time and find the largest adjacent gap.

Same pattern

←

Counting Sort 1

Continue · Next problem

Merge Sort: Counting Inversions