Digit Distribution Sorting — Problem Statement & Solution Guide

SortingHardCounting/Radix Sort

TimeO(n * k)

SpaceO(n + 10)

Problem Description

Given an array of non‑negative integers, reorder the elements so that they appear in non‑decreasing order. The sorting must be performed without using any comparison‑based algorithm; instead, employ a digit‑by‑digit distribution technique (i.e., counting sort applied to each decimal position). The input may contain duplicate values and the original relative order of equal elements does not need to be preserved. Return the sorted sequence.

DSA Pattern Breakdown

"Digit Distribution Sorting"

hard

WHY DOES IT MATTER?

Digit distribution (radix) sorting eliminates the comparison bottleneck, turning sorting into a series of linear passes. This pattern is essential when the key space is bounded (e.g., fixed‑size integers, strings of limited length) and when deterministic linear performance is required.

OPTIMIZATION CHALLENGE

The key insight is to combine a stable linear‑time bucket (counting) sort with digit extraction, ensuring that each pass refines the ordering without revisiting already sorted lower‑order digits, thereby reducing the overall complexity from O(n log n) to O(n·k).

REAL-WORLD CONNECTION

Think of sorting mail by zip code: first you group letters by the last digit of the zip, then by the next digit, and so on. Each grouping step is cheap and parallelizable, mirroring how radix sort buckets numbers by each decimal place.

When coding radix sort in an interview, pre‑compute the maximum number to know how many digit passes you need, reuse a single auxiliary array for counting to keep space low, and always verify stability by copying back to the original array after each pass.

COMPLEXITY AT A GLANCE

⏱ Time:O(n * k)

💾 Space:O(n + 10)

Core Theory — Why This Approach?

Radix sort is a non‑comparison based sorting technique that processes integers digit by digit, from the least significant digit (LSD) to the most significant digit (MSD). For each digit position a stable counting sort (or bucket sort) is applied, which groups numbers according to the current digit while preserving the relative order of previously processed digits. Because the algorithm never compares two whole numbers directly, its running time depends on the number of elements n and the number of digits k (or the maximum value’s logarithm base 10), yielding O(n·k) time, which is linear for fixed‑size integers. Naïve comparison sorts such as quicksort or mergesort incur O(n log n) time; on massive data sets where k is small (e.g., 32‑bit integers have at most 10 decimal digits), radix sort dramatically outperforms them, especially when the constant factors of counting sort are low.

The optimal paradigm emerges from two insights: (1) counting sort can sort a list of numbers in O(n + b) time where b is the range of keys—in this case b = 10 for a single decimal digit; (2) by chaining counting sorts for each digit, we avoid the logarithmic factor inherent to comparison sorts. The stability of each counting sort pass is crucial: it guarantees that after processing a higher‑order digit, the ordering established by lower‑order digits remains intact, ultimately producing a fully sorted array.

Interview Questions on This Problem

Q1How does radix sort achieve linear time complexity for sorting 32‑bit integers, and why does it outperform quicksort on large uniform datasets?

Radix sort processes each of the at most 10 decimal digits with a stable counting sort that runs in O(n + 10) = O(n). Since the number of digits k is bounded by a constant (10 for 32‑bit decimal numbers), the total time is O(k·n) = O(n). Quicksort, however, always incurs an O(n log n) factor due to comparisons, and its cache performance degrades on large uniform data because partitioning yields unbalanced sub‑arrays. Radix sort’s passes are cache‑friendly and avoid recursion, giving it a lower constant factor on massive uniform inputs.

Q2Explain why stability is mandatory in each counting‑sort pass of LSD radix sort. What would happen if an unstable sort were used?

Stability ensures that numbers with the same current digit retain the order established by previous (less significant) digits. If an unstable sort were used, the relative order of equal‑digit elements could be scrambled, breaking the invariant that lower‑order digits are already sorted. The final array would no longer be globally sorted, producing incorrect results.

Q3In a distributed system handling billions of log timestamps, how could you adapt digit distribution sorting to minimize network shuffling?

You can partition the data by most significant digit ranges (e.g., first two decimal digits) across nodes, run local counting sorts for each digit locally, and then concatenate partitions in digit order. Because each node only handles a bounded range, network traffic is limited to moving aggregated bucket counts, not the entire dataset, preserving the linear‑time advantage while scaling horizontally.

Examples

Example 1

Input

5
170 45 75 90 802

Output

45 75 90 170 802

Explanation: The maximum number has three digits, so three passes are required. Pass 1 (units place): counting sort groups numbers by their unit digit → [170, 90, 802, 45, 75]. Pass 2 (tens place): sorting the result by the tens digit yields → [45, 75, 90, 170, 802]. Pass 3 (hundreds place): final ordering by the hundreds digit gives → [45, 75, 90, 170, 802]. The array is now sorted.

Example 2

Input

8
3 0 1 4 1 5 9 2

Output

0 1 1 2 3 4 5 9

Explanation: The largest value (9) has one digit, so a single pass suffices. Counting sort on the only digit (units) distributes the numbers into buckets 0‑9, producing the ordered list [0, 1, 1, 2, 3, 4, 5, 9].

Example 3

Input

6
1000 100 10 1 0 999

Output

0 1 10 100 999 1000

Explanation: The maximum number (1000) has four digits, thus four passes are executed. Pass 1 (units): → [0, 1000, 10, 100, 1, 999] Pass 2 (tens): → [0, 1, 10, 1000, 100, 999] Pass 3 (hundreds): → [0, 1, 10, 100, 1000, 999] Pass 4 (thousands): → [0, 1, 10, 100, 999, 1000]. The final sequence is sorted.

Constraints

1 <= nums.length <= 100000
0 <= nums[i] <= 1000000000
All numbers are integers
The algorithm must run in O(n * d) time, where d is the number of decimal digits of the largest element

Optimal Approach & Strategy

Apply LSD radix sort: for each decimal digit, perform a stable counting sort that distributes numbers into ten buckets, then recombine. This runs in O(n·k) time, which is linear for fixed‑size integers.

Brute Force Approach

Use a standard comparison sort like quicksort or mergesort, which repeatedly compares pairs of elements to order them, yielding O(n log n) time.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n * k)

function solution(nums) {
   const RADIX = 10;
   let maxLength = false;
   let tmp, placement = 1, arr = [];

   // sort the array
   nums.forEach(function (num) {
      arr.push(num.toString().split(''));
   });

   arr.sort(function (a, b) {
      for (var placement = a.length - 1; placement >= 0; placement--) {
         if (a[placement] === b[placement]) {
            continue;
         } else {
            return b[placement] - a[placement];
         }
      }
      return 0;
   });

   // convert the array back to the string
   for (var i = 0; i < arr.length; i++) {
      tmp = arr[i].join('');
      nums[i] = parseInt(tmp);
   }

   return nums;
}

class Solution {
   public:
      int* solution(int* nums, int numsSize) {
         int RADIX = 10;
         bool maxLength = false;
         int placement = 1;
         int* arr = new int[numsSize];

         // sort the array
         for (int i = 0; i < numsSize; i++) {
            arr[i] = nums[i];
         }

         sort(arr, arr + numsSize, [](int a, int b) {
            string strA = to_string(a);
            string strB = to_string(b);
            for (int placement = strA.length() - 1; placement >= 0; placement--) {
               if (strA[placement] == strB[placement]) {
                  continue;
               } else {
                  return strB[placement] - strA[placement];
               }
            }
            return 0;
         });

         // convert the array back to the string
         for (int i = 0; i < numsSize; i++) {
            nums[i] = arr[i];
         }

         delete[] arr;
         return nums;
      }
}

class Solution {
   public int[] solution(int[] nums) {
      int RADIX = 10;
      boolean maxLength = false;
      int placement = 1;
      int[] arr = new int[nums.length];

      // sort the array
      for (int i = 0; i < nums.length; i++) {
         arr[i] = nums[i];
      }

      Arrays.sort(arr, new Comparator<Integer>() {
         public int compare(Integer a, Integer b) {
            String strA = String.valueOf(a);
            String strB = String.valueOf(b);
            for (int placement = strA.length() - 1; placement >= 0; placement--) {
               if (strA.charAt(placement) == strB.charAt(placement)) {
                  continue;
               } else {
                  return strB.charAt(placement) - strA.charAt(placement);
               }
            }
            return 0;
         }
      });

      // convert the array back to the string
      for (int i = 0; i < arr.length; i++) {
         nums[i] = arr[i];
      }

      return nums;
   }
}

def solution(nums):
   RADIX = 10
   maxLength = False
   placement = 1
   arr = []

   # sort the array
   for num in nums:
      arr.append(list(str(num)))

   arr.sort(key=lambda x: int(''.join(x)), reverse=True)

   # convert the array back to the string
   for i in range(len(arr)):
      tmp = ''.join(arr[i])
      nums[i] = int(tmp)

   return nums

function solution(nums) {
   const RADIX = 10;
   let maxLength = false;
   let tmp, placement = 1, arr = [];

   // sort the array
   nums.forEach(function (num) {
      arr.push(num.toString().split(''));
   });

   arr.sort(function (a, b) {
      for (var placement = a.length - 1; placement >= 0; placement--) {
         if (a[placement] === b[placement]) {
            continue;
         } else {
            return b[placement] - a[placement];
         }
      }
      return 0;
   });

   // convert the array back to the string
   for (var i = 0; i < arr.length; i++) {
      tmp = arr[i].join('');
      nums[i] = parseInt(tmp);
   }

   return nums;
}

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Digit Distribution Sorting Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Constraints

More Sorting

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Digit Distribution Sorting — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Solve in Interative Editor