Loading…

mediumArraysSometimes asked

The Full Counting Sort

Q: How do you solve The Full Counting Sort using the Bucket Lists in Input Order (Stable, Optimal) approach?

When to use it: The clean intended solution — 'append each string to its key's bucket as I scan, then concatenate buckets 0..99'. This is counting sort generalised to records. The integer is the sort key; the string rides along. **Step 1 — the '-' transform.** Scan items with their 0-based index `i`. If `i < n/2` (integer division), the string is replaced by `'-'`; otherwise it is kept. This must use the *original* index, so do it during the same scan that buckets the items, before any reordering. **Step 2 — bucket by key, in input order.** Maintain `100` lists (one per possible key). Append each item's string to `bucket[key]`. Crucially, because we scan the input left to right and *append*, two items with the same key land in their bucket in the same relative order they appeared — that is stability, for free, with no extra work. **Step 3 — emit ascending.** Walk buckets `0..99` and concatenate. Smaller keys come first; within a key, input order is preserved. Join the strings with single spaces and print. **Why not rebuild from counts?** Counting Sort 2's 'expand a histogram' trick regenerates the *value*, which would lose the attached string. To carry payloads you must store the actual strings — per-key lists (or prefix-sum placement) are the way. Time complexity: O(n + k). Space complexity: O(n + k).

Q: How do you solve The Full Counting Sort using the Prefix-Sum Stable Placement approach?

When to use it: Mention as the textbook stable counting sort and the building block of radix sort, especially if asked to avoid per-key dynamic lists. Same result without dynamic per-key lists — the classic CLRS counting sort, made stable. **Count, then prefix-sum.** Tally `count[key]` over all items. Convert to ending positions: `pos[key]` = number of items with key `≤ key`. Now `pos[key]-1` is the last output index for that key. **Place from the back.** Iterate items from index `n-1` down to `0`. For each item, decrement `pos[key]` and write the (dashed-or-kept) string at that index. Scanning backward with a decrementing end-position keeps earlier-input equal keys at earlier output indices — stable. **Why backward + end-positions = stable.** The last occurrence of a key is placed at the highest slot of its block first; as we move toward the front of the input, each earlier equal-key item takes the next-lower slot. The net effect preserves input order within each key. (Equivalently, use start-positions and scan forward.) **Why it matters.** This formulation is exactly one digit-pass of LSD radix sort. Chaining stable passes from least- to most-significant digit sorts large keys in linear time — and it only works because each pass is stable. Time complexity: O(n + k). Space complexity: O(n + k).

Arrays & Hashing · 61 of 83 · 9 min

You are given n items, each a pair (x, s) where x is an integer key in 0..99 and s is a string. Two transformations and a sort:

1
For the first half of the items (those with original 0-based index i < n/2), replace the string s with a single dash '-'.
2
Stably sort all items by their integer key x.
3
Print the resulting strings in order, separated by single spaces.

Stability means items sharing a key must appear in their original input order.

In plain English

This is counting sort upgraded from sorting bare integers to sorting records: the integer is the sort key, the string is data that must travel with its key. Two subtleties — the '-' replacement on the first half by 0-based index, and the strict requirement that equal keys retain input order (stability).

Examples

Example 1

Input: n = 20 0 ab 6 cd 0 ef 6 gh 4 ij 0 ab 6 cd 0 ef 6 gh 0 ij 4 that 3 be 0 to 1 be 5 question 1 or 2 not 4 is 2 to 4 the
Output: - - - - - to be or not to be - that is the question - - - -
Note: Indices 0..9 (first half) have their strings replaced by '-'. Then stable sort by key. Key 0 items keep input order, key 1 'be' before 'or', etc. The real strings to/be/or/not/to/be/that/is/the/question come from the second half.

Example 2

Input: n = 2 0 abc 0 def
Output: - def
Note: n/2 = 1, so index 0 ('abc') becomes '-'; index 1 keeps 'def'. Both have key 0; stability keeps '-' (was index 0) before 'def' (was index 1).

Constraints

1 ≤ n ≤ 10⁶ (n is even in the standard input)
0 ≤ x < 100
1 ≤ |s| ≤ 10, lowercase letters
Sort must be stable on the key x

Clarifying questions4First question: Which items get their string replaced by '-'?Explore questions

Q1.Which items get their string replaced by '-'?
Those in the first half by 0-based index: i < n/2 (integer division). The back half keeps its real string.
Q2.Is the index 0-based or 1-based for the half rule?
0-based. With n items, indices 0..n/2-1 are replaced; n/2..n-1 are kept.
Q3.Does the sort need to be stable?
Yes. Items with the same key must come out in their original input order — that is the defining requirement.
Q4.What is printed — keys or strings?
The strings, space-separated, in sorted-by-key order.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Each item is a pair `[key, value]` where the integer key is in 0..99 and the value is a string. Replace the string of every item in the FIRST HALF (index `i < n/2`) with '-', then stably counting-sort the items by key, and print the resulting strings space-separated. Stability is the crux: items with the same key must keep their original input order, which is exactly what bucketing-in-input-order (or prefix-sum placement) gives you.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you implement counting sort *stably* while carrying satellite data, and whether you correctly apply the index-based '-' transformation using 0-based n/2.

Where candidates slip

Losing stability (e.g. placing by reverse scan with forward-increment, or rebuilding from counts only), or replacing the wrong half / using 1-based indexing for the '-' rule.

How to stand out

Call out that appending to buckets while scanning forward is inherently stable, contrast with the prefix-sum + back-to-front placement formulation, and connect stability to radix sort correctness.

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	Bucket Lists in Input Order (Stable, Optimal)Optimal	`O(n + k)`	`O(n + k)`	The clean intended solution — 'append each string to its key's bucket as I scan, then concatenate buckets 0..99'.	Read
2	Prefix-Sum Stable Placement	`O(n + k)`	`O(n + k)`	Mention as the textbook stable counting sort and the building block of radix sort, especially if asked to avoid per-key dynamic lists.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewItem i = (x, s)i < n/2 ?YesNoExplore the full tree

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

Bucket Lists in Input Order (Stable, Optimal)

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

The clean intended solution — 'append each string to its key's bucket as I scan, then concatenate buckets 0..99'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Each item has a small integer key (0..99) and a string. How would you group strings by key without comparing keys?

2Hint 2Explore hint

Keep 100 lists. Scanning left to right, append each (possibly dashed) string to the list for its key.

3Hint 3Explore hint

Because you append in input order, equal keys stay ordered automatically. Concatenate lists 0..99 and join with spaces.

A · Core idea

This is counting sort generalised to records. The integer is the sort key; the string rides along.

Step 1 — the '-' transform. Scan items with their 0-based index i. If i < n/2 (integer division), the string is replaced by '-'; otherwise it is kept. This must use the original index, so do it during the same scan that buckets the items, before any reordering.

Step 2 — bucket by key, in input order. Maintain 100 lists (one per possible key). Append each item's string to bucket[key]. Crucially, because we scan the input left to right and append, two items with the same key land in their bucket in the same relative order they appeared — that is stability, for free, with no extra work.

Step 3 — emit ascending. Walk buckets 0..99 and concatenate. Smaller keys come first; within a key, input order is preserved. Join the strings with single spaces and print.

Why not rebuild from counts? Counting Sort 2's 'expand a histogram' trick regenerates the value, which would lose the attached string. To carry payloads you must store the actual strings — per-key lists (or prefix-sum placement) are the way.

B · Visual dry run

Interactive dry run

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

n = 4 → [(1,"a"), (0,"b"), (1,"c"), (0,"d")]

Array state

after scan

bucket0=['-','d'], bucket1=['-','c']

[0]

[1]

[2]

[3]

Current pointerResolved stateNot processed

Final result- d - c

C · Code with teaching comments

solution.javaJava

Bucket Lists in Input Order (Stable, Optimal) — optimal

3 teaching notes

1
public String fullCountingSort(int[] keys, String[] vals) {
2
    int n = keys.length;
3
    List<List<String>> buckets = new ArrayList<>();
4
    // Ascending key walk produces the sorted-by-key sequence.
5
    for (int v = 0; v < 100; v++) {
6
        buckets.add(new ArrayList<>());
7
    }
8
    for (int i = 0; i < n; i++) {
9
        // First-half rule on the ORIGINAL 0-based index; integer division n/2 splits
10
        // the halves.
11
        String s = (i < n / 2) ? "-" : vals[i];
12
        // Append in input order — this single line is what makes the sort stable.
13
        buckets.get(keys[i]).add(s);
14
    }
15
    StringBuilder sb = new StringBuilder();
16
    for (int v = 0; v < 100; v++) {
17
        for (String s : buckets.get(v)) {
18
            if (sb.length() > 0) sb.append(' ');
19
            sb.append(s);
20
        }
21
    }
22
    return sb.toString();
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

Appending to a per-key list while scanning forward is the simplest correct stable counting sort. Stability is not an add-on here — it falls out of the append order — and that same stability is what makes a multi-pass radix sort produce a correct final ordering.

ComplexityO(n + k) time, O(n + k) space — One pass to bucket all n strings is O(n); concatenating across k = 100 buckets touches each string once more, O(n + k) total time and O(n + k) space for the buckets and output.

E · Edge cases and pitfalls5all same key — One bucket holds every string in input order → output equals the (dashed) input order.Explore edge cases

Edge cases handled

all same keyOne bucket holds every string in input order → output equals the (dashed) input order.
n = 2, both key 0n/2 = 1 → index 0 dashed, index 1 kept; output '- <s1>'.

Pitfalls

Replacing strings using 1-based index or comparing i <= n/2 — off by one on the half boundary.
Sorting the (key, string) pairs with a comparison sort that is not stable — equal keys reorder.
Printing keys instead of strings, or forgetting single-space separation.

03.2

Approach 2 of 2

Prefix-Sum Stable Placement

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

Mention as the textbook stable counting sort and the building block of radix sort, especially if asked to avoid per-key dynamic lists.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Count items per key, then turn counts into starting output indices with a prefix sum.

2Hint 2Explore hint

To stay stable while placing into a flat array, scan the input from the LAST element to the FIRST and decrement the position for each key.

3Hint 3Explore hint

Carry the string into the computed slot so the payload travels with its key.

A · Core idea

Same result without dynamic per-key lists — the classic CLRS counting sort, made stable.

Count, then prefix-sum. Tally count[key] over all items. Convert to ending positions: pos[key] = number of items with key ≤ key. Now pos[key]-1 is the last output index for that key.

Place from the back. Iterate items from index n-1 down to 0. For each item, decrement pos[key] and write the (dashed-or-kept) string at that index. Scanning backward with a decrementing end-position keeps earlier-input equal keys at earlier output indices — stable.

Why backward + end-positions = stable. The last occurrence of a key is placed at the highest slot of its block first; as we move toward the front of the input, each earlier equal-key item takes the next-lower slot. The net effect preserves input order within each key. (Equivalently, use start-positions and scan forward.)

Why it matters. This formulation is exactly one digit-pass of LSD radix sort. Chaining stable passes from least- to most-significant digit sorts large keys in linear time — and it only works because each pass is stable.

B · Visual dry run

Interactive dry run

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

[(1,a),(0,b),(1,c),(0,d)] dashed first half → [(1,'-'),(0,'-'),(1,c),(0,d)]

Array state

final

out = ['-', d, '-', c]

[0]

[1]

[2]

[3]

Current pointerResolved stateNot processed

Final result- d - c

C · Code with teaching comments

Reference implementation previewpublic String fullCountingSortStable(int[] keys, String[] vals) { int n = keys.length; String[] payload = new String[n]; for (int i = 0; i < n; i++) { payload[i] = (i < n / 2) ? "-" : vals[i];Explore the full code

solution.javaJava

Prefix-Sum Stable Placement — reference

3 teaching notes

1
public String fullCountingSortStable(int[] keys, String[] vals) {
2
    int n = keys.length;
3
    String[] payload = new String[n];
4
    for (int i = 0; i < n; i++) {
5
        // Apply the first-half dash on original index before any reordering.
6
        payload[i] = (i < n / 2) ? "-" : vals[i];
7
    }
8
    int[] count = new int[100];
9
    for (int k : keys) {
10
        count[k]++;
11
    }
12
    int[] pos = new int[100];
13
    int running = 0;
14
    for (int v = 0; v < 100; v++) {
15
        running += count[v];
16
        // Prefix sum gives the END position (exclusive) of key v's block.
17
        pos[v] = running;
18
    }
19
    String[] out = new String[n];
20
    for (int i = n - 1; i >= 0; i--) {
21
        // Back-to-front placement with a decrementing end-index keeps equal keys
22
        // stable.
23
        out[--pos[keys[i]]] = payload[i];
24
    }
25
    return String.join(" ", out);
26
}

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

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

Prefix sums turn 'how many of each key' into 'where each key's block ends', and a back-to-front placement pass preserves ties. That is the canonical stable counting sort and the literal inner loop of radix sort.

ComplexityO(n + k) time, O(n + k) space — Counting and the prefix-sum pass are O(n + k); placing each of the n items is O(n). The output array and count/position arrays are O(n + k) space.

E · Edge cases and pitfalls5single key for all — One block of size n; reverse placement reproduces input order — stable.Explore edge cases

Edge cases handled

single key for allOne block of size n; reverse placement reproduces input order — stable.
keys 0 and 99 onlyTwo blocks at the ends of the output; middle keys contribute nothing.

Pitfalls

Computing the dash AFTER reordering — the index no longer reflects the original position.
Scanning forward with end-positions (or backward with start-positions) — breaks stability.
Using exclusive vs inclusive prefix sums inconsistently and overwriting slots.

Practice

Try the solution yourself

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

Editable code previewpublic String fullCountingSort(int[] keys, String[] vals) { int n = keys.length; List<List<String>> buckets = new ArrayList<>(); for (int v = 0; v < 100; v++) { buckets.add(new ArrayList<>());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.

Unstable sort on equal keys

The problem demands input order among equal keys. A generic sort that is not stable shuffles ties and fails.

Explore the code comparison

Don't write this

items.sort(key=lambda p: p[0])  # may reorder equal keys if not guaranteed stable in your impl

Write this instead

buckets = [[] for _ in range(100)]
for i, (k, s) in enumerate(items):
    buckets[k].append('-' if i < n // 2 else s)

Wrong half / off-by-one on the dash

The first half is 0-based indices 0..n/2-1. Using i <= n/2 or 1-based indexing dashes one item too many or too few.

Explore the code comparison

Don't write this

String s = (i <= n / 2) ? "-" : vals[i];

Write this instead

String s = (i < n / 2) ? "-" : vals[i];

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Stable counting sort by integer key carrying a string payload

Code pattern to memorize

for i, (k, s) in enumerate(items):
    s = '-' if i < n // 2 else s
    bucket[k].append(s)   # append preserves input order → stable
output = []
for k in 0..99: output += bucket[k]
print(' '.join(output))

Rules to remember

1Replace the string with '-' when the 0-based index i < n/2 (use integer division n // 2).
2Sort by key only; the string is satellite data carried along, never compared.
3Stability is mandatory: equal keys must stay in input order. Appending to per-key buckets while scanning left-to-right guarantees it.
4Walk buckets in ascending key order to emit the final sequence — that produces the sorted-by-key output.
5Output is the strings joined by spaces, not the keys.

Use this pattern when

Sorting records by a small bounded integer key while preserving ties' order
You need a stable linear-time sort
Building one digit-pass of radix sort
Keys are integers in a known small range and payloads must travel with them

Choose another pattern when

Key range is huge → bucket array is too big; use a stable comparison sort
No stability requirement and keys are bare integers → plain counting sort suffices
Keys are non-integer or unbounded → counting sort does not apply

Interview takeaway

Counting sort becomes a record sort the moment you carry payloads in per-key buckets in input order — and that stability is precisely what lets radix sort chain multiple passes correctly.

Continue

Transfer the pattern to another problem

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

Transferable patternStable counting sort with satellite data. Bucket records by a small integer key in input order (or place via prefix sums scanning back-to-front). Linear time when k is small; stability is mandatory and is exactly what radix sort chains across digit passes.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Counting Sort 2
The same stable counting sort but on bare integers without payloads.
Radix Sort (multi-digit)
Coming soon
Chain stable counting-sort passes from least to most significant digit.
Sort Characters By Frequency
Coming soon
Bucket by count, a sibling bucketing technique.

Same pattern

←

Quicksort 2 - Sorting (Partition)

Continue · Next problem

Anagram

mediumArraysSometimes asked

The Full Counting Sort

Arrays & Hashing · 61 of 83 · 9 min

You are given n items, each a pair (x, s) where x is an integer key in 0..99 and s is a string. Two transformations and a sort:

1
For the first half of the items (those with original 0-based index i < n/2), replace the string s with a single dash '-'.
2
Stably sort all items by their integer key x.
3
Print the resulting strings in order, separated by single spaces.

Stability means items sharing a key must appear in their original input order.

In plain English

Examples

Example 1

Input: n = 20 0 ab 6 cd 0 ef 6 gh 4 ij 0 ab 6 cd 0 ef 6 gh 0 ij 4 that 3 be 0 to 1 be 5 question 1 or 2 not 4 is 2 to 4 the
Output: - - - - - to be or not to be - that is the question - - - -
Note: Indices 0..9 (first half) have their strings replaced by '-'. Then stable sort by key. Key 0 items keep input order, key 1 'be' before 'or', etc. The real strings to/be/or/not/to/be/that/is/the/question come from the second half.

Example 2

Input: n = 2 0 abc 0 def
Output: - def
Note: n/2 = 1, so index 0 ('abc') becomes '-'; index 1 keeps 'def'. Both have key 0; stability keeps '-' (was index 0) before 'def' (was index 1).

Constraints

1 ≤ n ≤ 10⁶ (n is even in the standard input)
0 ≤ x < 100
1 ≤ |s| ≤ 10, lowercase letters
Sort must be stable on the key x

Clarifying questions4First question: Which items get their string replaced by '-'?Explore questions

Q1.Which items get their string replaced by '-'?
Those in the first half by 0-based index: i < n/2 (integer division). The back half keeps its real string.
Q2.Is the index 0-based or 1-based for the half rule?
0-based. With n items, indices 0..n/2-1 are replaced; n/2..n-1 are kept.
Q3.Does the sort need to be stable?
Yes. Items with the same key must come out in their original input order — that is the defining requirement.
Q4.What is printed — keys or strings?
The strings, space-separated, in sorted-by-key order.

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 implement counting sort *stably* while carrying satellite data, and whether you correctly apply the index-based '-' transformation using 0-based n/2.

Where candidates slip

Losing stability (e.g. placing by reverse scan with forward-increment, or rebuilding from counts only), or replacing the wrong half / using 1-based indexing for the '-' rule.

How to stand out

Call out that appending to buckets while scanning forward is inherently stable, contrast with the prefix-sum + back-to-front placement formulation, and connect stability to radix sort correctness.

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	Bucket Lists in Input Order (Stable, Optimal)Optimal	`O(n + k)`	`O(n + k)`	The clean intended solution — 'append each string to its key's bucket as I scan, then concatenate buckets 0..99'.	Read
2	Prefix-Sum Stable Placement	`O(n + k)`	`O(n + k)`	Mention as the textbook stable counting sort and the building block of radix sort, especially if asked to avoid per-key dynamic lists.	Read

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

Bucket Lists in Input Order (Stable, Optimal)

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

The clean intended solution — 'append each string to its key's bucket as I scan, then concatenate buckets 0..99'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Each item has a small integer key (0..99) and a string. How would you group strings by key without comparing keys?

2Hint 2Explore hint

Keep 100 lists. Scanning left to right, append each (possibly dashed) string to the list for its key.

3Hint 3Explore hint

Because you append in input order, equal keys stay ordered automatically. Concatenate lists 0..99 and join with spaces.

A · Core idea

This is counting sort generalised to records. The integer is the sort key; the string rides along.

Step 3 — emit ascending. Walk buckets 0..99 and concatenate. Smaller keys come first; within a key, input order is preserved. Join the strings with single spaces and print.

B · Visual dry run

Interactive dry run

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

n = 4 → [(1,"a"), (0,"b"), (1,"c"), (0,"d")]

Array state

after scan

bucket0=['-','d'], bucket1=['-','c']

[0]

[1]

[2]

[3]

Current pointerResolved stateNot processed

Final result- d - c

C · Code with teaching comments

solution.javaJava

Bucket Lists in Input Order (Stable, Optimal) — optimal

3 teaching notes

1
public String fullCountingSort(int[] keys, String[] vals) {
2
    int n = keys.length;
3
    List<List<String>> buckets = new ArrayList<>();
4
    // Ascending key walk produces the sorted-by-key sequence.
5
    for (int v = 0; v < 100; v++) {
6
        buckets.add(new ArrayList<>());
7
    }
8
    for (int i = 0; i < n; i++) {
9
        // First-half rule on the ORIGINAL 0-based index; integer division n/2 splits
10
        // the halves.
11
        String s = (i < n / 2) ? "-" : vals[i];
12
        // Append in input order — this single line is what makes the sort stable.
13
        buckets.get(keys[i]).add(s);
14
    }
15
    StringBuilder sb = new StringBuilder();
16
    for (int v = 0; v < 100; v++) {
17
        for (String s : buckets.get(v)) {
18
            if (sb.length() > 0) sb.append(' ');
19
            sb.append(s);
20
        }
21
    }
22
    return sb.toString();
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

E · Edge cases and pitfalls5all same key — One bucket holds every string in input order → output equals the (dashed) input order.Explore edge cases

Edge cases handled

all same keyOne bucket holds every string in input order → output equals the (dashed) input order.
n = 2, both key 0n/2 = 1 → index 0 dashed, index 1 kept; output '- <s1>'.

Pitfalls

Replacing strings using 1-based index or comparing i <= n/2 — off by one on the half boundary.
Sorting the (key, string) pairs with a comparison sort that is not stable — equal keys reorder.
Printing keys instead of strings, or forgetting single-space separation.

03.2

Approach 2 of 2

Prefix-Sum Stable Placement

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

Mention as the textbook stable counting sort and the building block of radix sort, especially if asked to avoid per-key dynamic lists.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Count items per key, then turn counts into starting output indices with a prefix sum.

2Hint 2Explore hint

To stay stable while placing into a flat array, scan the input from the LAST element to the FIRST and decrement the position for each key.

3Hint 3Explore hint

Carry the string into the computed slot so the payload travels with its key.

A · Core idea

Same result without dynamic per-key lists — the classic CLRS counting sort, made stable.

Count, then prefix-sum. Tally count[key] over all items. Convert to ending positions: pos[key] = number of items with key ≤ key. Now pos[key]-1 is the last output index for that key.

B · Visual dry run

Interactive dry run

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

[(1,a),(0,b),(1,c),(0,d)] dashed first half → [(1,'-'),(0,'-'),(1,c),(0,d)]

Array state

final

out = ['-', d, '-', c]

[0]

[1]

[2]

[3]

Current pointerResolved stateNot processed

Final result- d - c

C · Code with teaching comments

solution.javaJava

Prefix-Sum Stable Placement — reference

3 teaching notes

1
public String fullCountingSortStable(int[] keys, String[] vals) {
2
    int n = keys.length;
3
    String[] payload = new String[n];
4
    for (int i = 0; i < n; i++) {
5
        // Apply the first-half dash on original index before any reordering.
6
        payload[i] = (i < n / 2) ? "-" : vals[i];
7
    }
8
    int[] count = new int[100];
9
    for (int k : keys) {
10
        count[k]++;
11
    }
12
    int[] pos = new int[100];
13
    int running = 0;
14
    for (int v = 0; v < 100; v++) {
15
        running += count[v];
16
        // Prefix sum gives the END position (exclusive) of key v's block.
17
        pos[v] = running;
18
    }
19
    String[] out = new String[n];
20
    for (int i = n - 1; i >= 0; i--) {
21
        // Back-to-front placement with a decrementing end-index keeps equal keys
22
        // stable.
23
        out[--pos[keys[i]]] = payload[i];
24
    }
25
    return String.join(" ", out);
26
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.26 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 of the n items is O(n). The output array and count/position arrays are O(n + k) space.

E · Edge cases and pitfalls5single key for all — One block of size n; reverse placement reproduces input order — stable.Explore edge cases

Edge cases handled

single key for allOne block of size n; reverse placement reproduces input order — stable.
keys 0 and 99 onlyTwo blocks at the ends of the output; middle keys contribute nothing.

Pitfalls

Computing the dash AFTER reordering — the index no longer reflects the original position.
Scanning forward with end-positions (or backward with start-positions) — breaks stability.
Using exclusive vs inclusive prefix sums inconsistently and overwriting slots.

Practice

Try the solution yourself

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

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.

Unstable sort on equal keys

The problem demands input order among equal keys. A generic sort that is not stable shuffles ties and fails.

Explore the code comparison

Don't write this

items.sort(key=lambda p: p[0])  # may reorder equal keys if not guaranteed stable in your impl

Write this instead

buckets = [[] for _ in range(100)]
for i, (k, s) in enumerate(items):
    buckets[k].append('-' if i < n // 2 else s)

Wrong half / off-by-one on the dash

The first half is 0-based indices 0..n/2-1. Using i <= n/2 or 1-based indexing dashes one item too many or too few.

Explore the code comparison

Don't write this

String s = (i <= n / 2) ? "-" : vals[i];

Write this instead

String s = (i < n / 2) ? "-" : vals[i];

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Stable counting sort by integer key carrying a string payload

Code pattern to memorize

for i, (k, s) in enumerate(items):
    s = '-' if i < n // 2 else s
    bucket[k].append(s)   # append preserves input order → stable
output = []
for k in 0..99: output += bucket[k]
print(' '.join(output))

Rules to remember

1Replace the string with '-' when the 0-based index i < n/2 (use integer division n // 2).
2Sort by key only; the string is satellite data carried along, never compared.
3Stability is mandatory: equal keys must stay in input order. Appending to per-key buckets while scanning left-to-right guarantees it.
4Walk buckets in ascending key order to emit the final sequence — that produces the sorted-by-key output.
5Output is the strings joined by spaces, not the keys.

Use this pattern when

Sorting records by a small bounded integer key while preserving ties' order
You need a stable linear-time sort
Building one digit-pass of radix sort
Keys are integers in a known small range and payloads must travel with them

Choose another pattern when

Key range is huge → bucket array is too big; use a stable comparison sort
No stability requirement and keys are bare integers → plain counting sort suffices
Keys are non-integer or unbounded → counting sort does not apply

Interview takeaway

Counting sort becomes a record sort the moment you carry payloads in per-key buckets in input order — and that stability is precisely what lets radix sort chain multiple passes correctly.

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 2
The same stable counting sort but on bare integers without payloads.
Radix Sort (multi-digit)
Coming soon
Chain stable counting-sort passes from least to most significant digit.
Sort Characters By Frequency
Coming soon
Bucket by count, a sibling bucketing technique.

Same pattern

←

Quicksort 2 - Sorting (Partition)

Continue · Next problem

Anagram