Where it runs
1. The problem
Counting sort from the last lesson is fast, but it has a weak spot. It keeps one counter for every possible value, from 0 up to the largest number. For numbers up to 9 that is 10 cells, and all is well. For ids (identification numbers) up to a billion it is a billion cells. A program rarely has that much memory to spare.
Yet those big ids have few digits. A number up to a billion has 10 digits at most. So the question is this: can you sort by looking at one digit at a time instead of the whole number at once?
You have 200,000 order ids, each one 9,999,999 or less. You want them sorted, and fast, without an array of ten million counters.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedRecognise it
Say these words and it is this pattern
- keys are integers in a small known range
- sort ages, grades, or bounded counts
- need O(n) and comparisons are the bottleneck
- sort by digit or fixed-width key
- n large but the value range is much smaller than n
Looks similar, isn't
- Fast sort (merge / quick)
No comparison sort can beat n log n. Reading the key steps around that limit entirely.
- Hash set / map
A map counts values too, but it keeps no order. Counting sort uses the value as an index.
- Sort with a custom comparator
A comparator describes the order between two items. Counting sort never looks at two items.
- Elementary sorts (selection, bubble, insertion)
Those compare neighbours and cost n squared. Counting sort is linear when the range allows it.
n values with keys under k gives O(n + k). Radix sort costs O(d times n) across d digits.
On LeetCode
Problems that sort large whole numbers or digit strings of one length in linear time, where a full tally would be too big. Sort by one digit per pass and keep ties in their order.
The statement asks for linear time, so radix sort the numbers and compare neighbours.
Its follow-up asks for radix sort by name, sorting the digit strings from the last digit up.
Add 50000 to every value so none is negative, then radix sort.