Log inSign up
mediumGeeksforGeeksNot Started

Radix Sort

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on GeeksforGeeks
Lesson

Problem Statement

Given an array of integers nums, sort the array in ascending order using the Radix Sort algorithm.

You must implement a non-comparison based integer sorting algorithm using LSD (Least Significant Digit) Radix Sort with a time complexity of **O(D * (N + K))**, where D is the maximum number of digits and K is the numerical base (e.g. 10).

Example 1:

Input: nums = [170, 45, 75, 90, 802, 24, 2, 66]
Output: [2, 24, 45, 66, 75, 90, 170, 802]
Explanation: Sorted digit by digit from units place up to hundreds place.

Example 2:

Input: nums = [5, 2, 3, 1]
Output: [1, 2, 3, 5]
Explanation: Single digit numbers sorted directly by counting sort digit pass.

Example 3:

Input: nums = [-5, -10, 0, 15, 3]
Output: [-10, -5, 0, 3, 15]
Explanation: Handling signed integers using an offset or negative separation strategy.

Constraints:

  • 1 <= nums.length <= 5 * 104
  • -5 * 104 <= nums[i] <= 5 * 104

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Stable Counting Sort mechanics
  • Positional numeral systems and digit extraction using modulo and integer division
  • Understanding non-comparison sorting lower bounds

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why non-comparison sorting can achieve linear O(N) time when D is constant.
  • Master why stability is an absolute requirement for the digit sorting subroutine in LSD Radix Sort.
  • Handle negative integer values in Radix Sort using an offset normalization technique.
  • Analyze Radix Sort complexity vs QuickSort and MergeSort across different dataset sizes.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Sorting integers or fixed-length strings where keys have bounded digit length D << N.
  • Beating the Omega(N log N) theoretical comparison sort lower bound.
  • Linear time sorting requirement for large datasets of numbers.

Algorithmic Decision Tree:

  • If keys are floating point numbers uniformly distributed in [0, 1) -> Bucket Sort.
  • If key range K is very small (K <= N) -> Direct Counting Sort.
  • If numbers have bounded length D and range is large -> Radix Sort O(D * (N + K)).

Connected Patterns:

Maximum Gap (Bucket / Radix Sort application)Bucket SortSort an Array

1. String Bucket Radix Sort (Brute Force)

Intuition

Find the maximum number of digits d. Pad all numbers with leading zeroes as strings. Starting from least significant digit to most significant digit, distribute numbers into 10 buckets (0 to 9) and collect them back. Repeat for all d digit places.

When to apply: Use to understand digit-by-digit distribution intuitively.

Iterative Selection Passes (O(N^2) Time)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Selection sort places the absolute minimum at the start
Visual state
Values and pointers at this exact step
pointers
S
170
45
75
90
802
24
2
66
0
1
2
3
4
5
6
↑ min
7
Variables at this step
pass
0
minVal
2
sortedCount
1
Check / comparison
Pass 0: Scan array to find global minimum: value 2 at index 6
Decision / next transition
Swap 2 with nums[0] (170). Sorted prefix: [2].
Why this step matters

Selection sort places the absolute minimum at the start.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public int[] radixSort(int[] nums) {
6 int max = 0;
7 for (int x : nums) max = Math.max(max, x);
8
9 for (int exp = 1; max / exp > 0; exp *= 10) {
10 List<List<Integer>> buckets = new ArrayList<>();
11 for (int i = 0; i < 10; i++) buckets.add(new ArrayList<>());
12 for (int x : nums) {
13 int digit = (x / exp) % 10;
14 buckets.get(digit).add(x);
15 }
16 int idx = 0;
17 for (List<Integer> b : buckets) {
18 for (int x : b) nums[idx++] = x;
19 }
20 }
21 return nums;
22 }
23 }
24
25 public static void main(String[] args) {
26 Solution sol = new Solution();
27 int[] nums = {170, 45, 75, 90, 802, 24, 2, 66};
28 System.out.println("Radix sorted: " + Arrays.toString(sol.radixSort(nums)));
29 }
30}

Time & Space Complexity

  • Time complexity: O(d * (n + b)) — d passes where each pass places n items into 10 buckets.
  • Space complexity: O(n) — O(n) auxiliary memory for bucket collections.

Why Brute Force Doesn't Scale:

Standard comparison sorts hit the theoretical Omega(N log N) decision tree lower bound. When integers have fixed word length (e.g. 32-bit integers, where D <= 4 with base 256), Radix Sort runs in strictly O(N) linear time using bitwise shift and mask (>> and & 0xFF).

For N = 10,000,000 32-bit integers: QuickSort requires ~240,000,000 operations; Base-256 Radix Sort (4 passes) requires ~40,000,000 operations (~6x faster).

2. MSD (Most Significant Digit) Recursive Radix Sort

Intuition

Determine the maximum place value. Partition numbers into 10 buckets according to their highest digit place. Recursively sort each bucket at the next lower digit place until all digits are exhausted.

When to apply: Use for lexicographical sorting or variable-length keys.

Standard Comparison Merge Sort (O(N log N) Time)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Divide-and-conquer splits problem size in half
Visual state
Values and pointers at this exact step
pointers
S
170
45
75
90
802
24
2
66
0
↑ leftHalf
1
2
3
4
↑ rightHalf
5
6
7
Variables at this step
stage
divide
leftSize
4
rightSize
4
Check / comparison
Divide array of length 8 into two halves of size 4
Decision / next transition
Left: [170, 45, 75, 90], Right: [802, 24, 2, 66].
Why this step matters

Divide-and-conquer splits problem size in half.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public int[] radixSort(int[] nums) {
6 int max = 0;
7 for (int x : nums) max = Math.max(max, x);
8 int exp = 1;
9 while (max / exp >= 10) exp *= 10;
10 msdSort(nums, 0, nums.length - 1, exp);
11 return nums;
12 }
13
14 private void msdSort(int[] nums, int l, int r, int exp) {
15 if (l >= r || exp <= 0) return;
16 List<List<Integer>> buckets = new ArrayList<>();
17 for (int i = 0; i < 10; i++) buckets.add(new ArrayList<>());
18 for (int i = l; i <= r; i++) {
19 int digit = (nums[i] / exp) % 10;
20 buckets.get(digit).add(nums[i]);
21 }
22 int k = l;
23 int[] starts = new int[10];
24 int[] ends = new int[10];
25 for (int d = 0; d < 10; d++) {
26 starts[d] = k;
27 for (int x : buckets.get(d)) nums[k++] = x;
28 ends[d] = k - 1;
29 }
30 for (int d = 0; d < 10; d++) {
31 if (starts[d] < ends[d]) {
32 msdSort(nums, starts[d], ends[d], exp / 10);
33 }
34 }
35 }
36 }
37
38 public static void main(String[] args) {
39 Solution sol = new Solution();
40 int[] nums = {170, 45, 75, 90, 802, 24, 2, 66};
41 System.out.println("MSD sorted: " + Arrays.toString(sol.radixSort(nums)));
42 }
43}

Time & Space Complexity

  • Time complexity: O(d * (n + b)) — d levels of recursion across n numbers.
  • Space complexity: O(n + d) — Recursion call stack and partition buckets.

3. LSD Counting Sort (Optimal & Standard)

Intuition

1. Find the maximum element to determine the number of digits. 2. For exp = 1, 10, 100... while max / exp > 0: run stable counting sort by digit (num / exp) % 10. 3. Count frequencies in count[10], compute prefix sums in count to determine output positions, and populate output array from back to preserve stability.

When to apply: Use as the clean StudyVex Gold Standard for Radix Sort.

LSD Radix Sort with Counting Buckets (O(D * (N + B)) Time)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
LSD radix sort processes numbers position by position without comparison
Visual state
Values and pointers at this exact step
pointers
S
170
45
75
90
802
24
2
66
0
↑ exp=1
1
2
3
4
5
6
7
Variables at this step
maxVal
802
maxDigits
3
exp
1
Check / comparison
Find maximum value: 802 (3 digits). Radix sort requires 3 passes (exp = 1, 10, 100)
Decision / next transition
Start Pass 1: sort by ones digit (exp = 1).
Why this step matters

LSD radix sort processes numbers position by position without comparison.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public int[] radixSort(int[] nums) {
6 int max = 0;
7 for (int x : nums) max = Math.max(max, x);
8
9 int n = nums.length;
10 int[] output = new int[n];
11
12 for (int exp = 1; max / exp > 0; exp *= 10) {
13 int[] count = new int[10];
14 for (int i = 0; i < n; i++) {
15 count[(nums[i] / exp) % 10]++;
16 }
17 for (int i = 1; i < 10; i++) {
18 count[i] += count[i - 1];
19 }
20 for (int i = n - 1; i >= 0; i--) {
21 int digit = (nums[i] / exp) % 10;
22 output[count[digit] - 1] = nums[i];
23 count[digit]--;
24 }
25 for (int i = 0; i < n; i++) {
26 nums[i] = output[i];
27 }
28 }
29 return nums;
30 }
31 }
32
33 public static void main(String[] args) {
34 Solution sol = new Solution();
35 int[] nums = {170, 45, 75, 90, 802, 24, 2, 66};
36 System.out.println("Radix sorted: " + Arrays.toString(sol.radixSort(nums)));
37 }
38}

Time & Space Complexity

  • Time complexity: O(d * (n + k)) — d passes where each pass performs linear counting sort on base k = 10.
  • Space complexity: O(n + k) — Output buffer of size n and count table of size 10.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force (Comparison Sort)O(N log N)O(1) to O(N)Sort using standard library Dual-Pivot QuickSort or Timsort.Pairwise element comparisons.
2.Better (MSD Most Significant Digit Radix Sort)O(D * (N + K))O(N + D * K) call stackSort starting from the most significant digit down, recursively partitioning into sub-buckets.Recursive partitioning tree overhead.
3.Optimal (LSD Least Significant Digit Radix Sort with Offset)OptimalO(D * (N + K))O(N + K)Iterate exponent exp = 1, 10, 100... up to maxVal, stably sorting with Counting Sort at each digit.Digit extraction and prefix sum passes.

Common Pitfalls & Crucial Edge Cases

Using an unstable sorting subroutine for LSD

If the digit sorting routine is not stable, higher-order passes destroy the relative ordering established by lower-order passes.

Iterating forward instead of backward when building output in Counting Sort

Scanning output from index 0 to n-1 in Counting Sort reverses duplicate elements and violates stability.

Ignoring negative numbers

Modulo of negative numbers in C++/Java can produce negative digit indices (-15 % 10 == -5), causing buffer index out of bounds exceptions unless offset is applied.

Crucial Edge Cases to Validate:

  • Negative Numbers ([-5, -10, 0, 15, 3]): Handled cleanly by adding offset = -minVal before radix passes and subtracting after.
  • Already Sorted Array ([1, 2, 3, 4, 5]): Completes in O(D * N) time without unnecessary pointer swaps.
  • Single Element Array ([42]): Loop executes for D passes and preserves element in O(1).
  • Numbers with Differing Digit Lengths ([1, 10, 100, 1000]): Modulo arithmetic treats missing high digits naturally as leading 0s.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why MUST the digit sorting subroutine in LSD Radix Sort be STABLE?

2.What is the time complexity of LSD Radix Sort for N numbers with at most D digits in base K?

3.How can Radix Sort easily support negative numbers without altering the core digit extraction logic?

Back to DSA Sheet