Radix-Sort Serial Numbers
MediumSorting & Searching
Problem
A factory scanner reads product serial numbers, non-negative integers below 2^31, and must emit them in ascending order. The firmware has no comparison-based sort; you are asked to implement radix sort.
Given serials, return them sorted in non-decreasing order using a least-significant-digit radix sort (any fixed base you like).
Example 1
- Input:
- serials = [170, 45, 75, 90, 802, 24, 2, 66]
- Output:
- [2, 24, 45, 66, 75, 90, 170, 802]
In base 10: sort stably by the units digit, then by the tens digit, then by the hundreds digit.
Example 2
- Input:
- serials = [0, 0, 1]
- Output:
- [0, 0, 1]
Constraints
- 0 ≤ serials.length ≤ 10^5
- 0 ≤ serials[i] < 2^31
- Do not call the language's built-in sort.
Hint
Show the first hint
Sorting by one digit at a time is easy with counting sort. In which order should you process the digits?
Walkthrough
How to approach it
01Clarify before coding
- Are numbers non-negative? Yes, which keeps the digit extraction simple.
- Which base? Any fixed base; 256 gives 4 passes for 31-bit values with a tiny count table.
- Can the list be empty? Yes.
02Brute force
Insertion sort or another hand-written comparison sort.
Cost: O(n²) for insertion sort; O(n log n) for merge sort. Radix sort achieves O(d · (n + b)) with d digits in base b.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.