Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
You are given a list of integers, every value in the range 0..99. Build a frequency array of fixed size 100, walk the input once, and do `freq[value]++`. Return the 100-element frequency list. No comparisons, no sorting — just bucketed tallies in O(n) time and O(k) space where k = 100.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you recognise that a bounded value range lets you replace comparison sorting with direct array indexing, and whether you read the output spec (a length-100 frequency list, not a sorted array).
Where candidates slip
Sizing the array to max(arr)+1 (then crashing if all values are small) or returning the sorted array instead of the requested frequency list.
How to stand out
Name it as the count phase of counting sort, note it is non-comparison-based and O(n + k), and mention it generalises to radix sort for larger keys.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewNeed counts of each valueIs the value range small and bounded?YesNoExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 1 · Optimal
Frequency Array (Bucket Tally)
1Hint 1Explore hintHide hint
Every value is in 0..99. If you had 100 mailboxes, one per value, how would you tally occurrences?
2Hint 2Explore hintHide hint
Create an array of 100 zeros. For each input value x, increment the slot at index x.
3Hint 3Explore hintHide hint
Return the whole 100-slot array — slots for values that never appeared stay 0.
A · Core idea
Counting sort's first phase is a histogram. We exploit the promise that every value lies in 0..99: allocate an array freq of 100 zeros and, for each input value x, do freq[x]++.
Why indexing by value works. In a comparison sort we ask 'is a < b?' repeatedly — that costs at least n log n. Here we never compare; the value is the address of its own counter. Reading freq[x] and incrementing it is O(1), so counting all n values is O(n).
Why the array is exactly size 100. The constraint fixes the value universe to 0..99, so 100 slots cover every possibility. We do not size it to max(arr) + 1: the spec demands a length-100 result, and any value that never appears must still be reported as a 0 count at its index.
Why this is not 'cheating' the sort lower bound. The Ω(n log n) bound applies only to comparison-based sorts. Counting sort sidesteps it by using values as indices, trading the small extra O(k) space for linear time — a worthwhile deal whenever k is small.
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
after first 1
freq[1] = 1
freq = [0, 3, 1, 1, 0, ..., 0]C · Code with teaching comments
D · Why it works and complexityO(n + k) timeO(k) spaceOpen the invariant and proofExplore the proofHide the proof
The value doubles as its own array index. That single idea — 'use the value to address its bucket' — is the seed of counting sort, radix sort, and bucket sort. Whenever the key space is small and integral, reach for an array instead of comparisons.
ComplexityO(n + k) time, O(k) space — One pass over n elements to count, plus allocating and returning the k = 100 buckets, so O(n + k) time and O(k) space — here k is the constant 100.
E · Edge cases and pitfalls5arr = [0, 0, 0] — freq[0] = 3, all other buckets 0 — value 0 indexes the first slot correctly.Explore edge casesHide edge cases
Edge cases handled
arr = [0, 0, 0]freq[0] = 3, all other buckets 0 — value 0 indexes the first slot correctly.arr = [99]freq[99] = 1 — confirms the array must hold index 99, so size 100.
Pitfalls
- Sizing the array to max(arr)+1 instead of the fixed 100 — fails the length-100 output spec.
- Returning the sorted array instead of the frequency list.
- Off-by-one: using size 99 and overflowing on value 99.
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 playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Dynamic size instead of fixed 100
The output contract is a length-100 list. Sizing to max(arr)+1 produces a shorter array when the largest value is below 99 and drops the trailing zero buckets.
Explore the code comparisonHide the code comparison
Dynamic size instead of fixed 100
The output contract is a length-100 list. Sizing to max(arr)+1 produces a shorter array when the largest value is below 99 and drops the trailing zero buckets.
Don't write this
freq = [0] * (max(arr) + 1)
for x in arr:
freq[x] += 1Write this instead
freq = [0] * 100
for x in arr:
freq[x] += 12Returning sorted values, not counts
The problem asks for the histogram, not the ordered array. Returning the sorted list is the wrong output type.
Explore the code comparisonHide the code comparison
Returning sorted values, not counts
The problem asks for the histogram, not the ordered array. Returning the sorted list is the wrong output type.
Don't write this
Arrays.sort(arr);
return arr;Write this instead
int[] freq = new int[100];
for (int x : arr) freq[x]++;
return freq;Revise
Carry the pattern into the interview
Pattern to remember
Frequency array (bucket tally) over a bounded value range
Code pattern to memorize
freq = [0] * 100
for x in arr:
freq[x] += 1
return freqRules to remember
- 1The output is the frequency list of length 100, not the sorted array — read the spec carefully.
- 2The value range is fixed at
0 ≤ x < 100, so the array size is the constant100, nevermax(arr)+1here. - 3Index the bucket array by the value itself:
freq[x]++. The value is the key. - 4This is the counting half of counting sort — Counting Sort 2 reconstructs the sorted list from these tallies.
- 5Single pass, no comparisons. Counting sort is not comparison-based, so the Ω(n log n) lower bound does not apply.
Use this pattern when
- Values come from a small, known, bounded integer range
- You only need counts / histogram, not a full ordering
- You want linear-time tallying without sorting
- Preparing the count table for a later stable counting sort
Choose another pattern when
- Value range is huge or unbounded → a hash map or comparison sort fits better
- Values are floats or arbitrary objects → no integer index to bucket on
- You need the actual sorted sequence now → that is Counting Sort 2
Interview takeaway
When values live in a small fixed range, an array indexed by value turns counting into O(n) bucket increments — the foundation every counting / radix sort builds on.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternFrequency array. When keys come from a small bounded integer range, index an array by the key to count in O(n). This is the count phase shared by counting sort, radix sort, and bucket sort.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Counting Sort 2Use this frequency array to reconstruct the fully sorted list.
- The Full Counting SortStable counting sort by an integer key while carrying string payloads.
- Sort Colors (Dutch National Flag)Coming soonCounting sort with only 3 buckets — or a one-pass three-way partition.