Radix Sort Problems
3 Radix Sort LeetCode problems · Browse tasks by difficulty and choose your next practice problem.
Learn the coding interview patterns behind these problems.
Sort digits while preserving earlier work
Least-significant-digit radix sort processes one digit at a time, from right to left. Each pass must be stable: equal digits keep the relative order established by earlier passes. This lets local digit ordering accumulate into full numeric or fixed-width string ordering.
When to use it
Consider radix sorting for bounded-width integers or equal-length digit strings. Kth Smallest Trimmed Number uses suffixes of numeric strings, making stable right-to-left passes especially relevant when queries ask about different trim lengths.
Worked example
Sort [31, 12, 22, 11] using base-10 digits.
- Sort stably by units: [31, 11, 12, 22]. The two values ending in 1 retain their original order.
- Sort that sequence stably by tens: [11, 12, 22, 31]. The tens-1 group retains the units order.
- All numbers have two digits, so the second pass completes the sort.
The final order is [11, 12, 22, 31]. An unstable second pass could incorrectly put 12 before 11.
Time and space
With counting sort for each digit, d passes over n items in base b take O(d × (n + b)) time and O(n + b) auxiliary space. Calling this linear assumes d and b are bounded; they are part of the cost otherwise.
Mistakes to check
- Do not replace a stable digit pass with an arbitrary unstable sort. Stability is the invariant that makes LSD radix sorting work.
- Keep trimmed numbers as digit strings when leading zeros or original-index tie rules matter; conversion to a fixed-width integer may also overflow.
- Negative integers and variable-length strings need an explicit representation and ordering rule; the unsigned equal-width example does not handle them automatically.
Further reading: NIST Dictionary of Algorithms: radix sort
Guide reviewed .