Custom Digit Sorting — Problem Statement & Solution Guide

SortingHardCounting/Radix Sort

TimeO(n · k + n)

SpaceO(n + customBase)

Problem Description

Given an array of non-negative integers and two integers, customBase and k, implement a custom radix sort to sort the array. The custom radix sort should use the customBase and should not consider more than k digits for sorting. If a number cannot be represented in the customBase within k digits, it should be placed at the end of the sorted array in their original order.

DSA Pattern Breakdown

"Custom Digit Sorting"

hard

WHY DOES IT MATTER?

The custom digit sorting pattern demonstrates how to adapt linear‑time bucket sorts to real‑world constraints such as limited precision, memory caps, or domain‑specific digit relevance, making it a versatile tool for high‑throughput pipelines.

OPTIMIZATION CHALLENGE

The breakthrough is recognizing that numbers exceeding the k‑digit window can be excluded from the counting passes entirely, turning a potentially O(n · log max) process into a strict O(n · k) routine while preserving stability for overflow elements.

REAL-WORLD CONNECTION

Think of a postal sorting center that only reads the first k characters of a zip code to route mail to regional hubs; packages with longer zip codes are sent to a special overflow lane for manual handling. This mirrors the algorithm’s early‑digit bucket passes and the stable overflow bucket.

During an interview, implement the digit extraction as a pure integer operation (num / pow(base, i) % base) and reuse a single auxiliary array for counting; this avoids costly string conversions and keeps the constant factors low.

COMPLEXITY AT A GLANCE

⏱ Time:O(n · k + n)

💾 Space:O(n + customBase)

Core Theory — Why This Approach?

Custom radix sort extends the classic LSD (least‑significant‑digit) radix sort by allowing an arbitrary numeric base (customBase) and a hard limit on the number of digit positions (k) that participate in the sorting process. In a traditional radix sort, each integer is decomposed into its digits in base 10 (or base 2⁸ for byte‑wise implementations) and the algorithm performs a stable counting sort for every digit position, guaranteeing O(n · d) time where d is the number of digits needed to represent the largest element. When the base is variable and the digit count is capped, the algorithm must gracefully handle numbers that would overflow the k‑digit window; these overflow elements are excluded from the counting passes and appended unchanged, preserving their original relative order (a stable “out‑of‑range” bucket). This design prevents the algorithm from degrading to O(n · log_{customBase} maxValue) on inputs with extremely large values, which would otherwise blow up the number of passes.

Naïve approaches—such as converting every integer to a string in the custom base and then using a comparator that looks at the first k characters—incur O(n · k) time for conversion plus O(n log n) for the sort, which is prohibitive for large n (e.g., n ≥ 10⁶). Moreover, string‑based sorting loses the stability guarantees needed for the overflow bucket. The optimal paradigm leverages counting sort’s linear‑time bucket aggregation per digit, combined with a pre‑filter that tags overflow numbers. By iterating only k times over the array and using O(customBase) auxiliary space for the count array, the algorithm achieves true linear performance relative to n, independent of the magnitude of the numbers beyond the k‑digit window.

Interview Questions on This Problem

Q1How would you modify a standard LSD radix sort to support an arbitrary base and a maximum of k digit passes, while ensuring numbers that need more than k digits stay in their original order at the end?

Introduce a preprocessing step that flags any number whose representation in the custom base exceeds k digits. Those flagged numbers are collected in a separate list preserving input order. For the remaining numbers, perform k passes of stable counting sort using the custom base, extracting the i‑th digit via (num / base^i) % base. After the k passes, concatenate the sorted list with the overflow list.

Q2Why does a counting‑sort based radix implementation remain O(n) even when the custom base is large (e.g., base = 10⁵), and what space considerations arise?

Counting sort’s time per pass is O(n + base) because it builds a frequency array of size equal to the base. When base is large, the O(base) term dominates, but it is still linear with respect to the input size if base is bounded by a reasonable constant (e.g., ≤ 10⁶). The space cost is O(base) for the count array plus O(n) for the temporary output buffer; careful allocation or reusing buffers can keep total auxiliary space O(n + base).

Q3In a distributed system that shards data by numeric keys, how could the custom digit sorting technique be used to efficiently route keys to shards when only the most significant k digits matter?

Treat each shard as a bucket corresponding to a prefix of length k in the chosen base. By extracting the first k digits of each key (most‑significant‑digit order) and performing a single pass of counting sort (or direct bucket assignment), you can route keys to the correct shard in O(n) time without full key comparison. Keys whose prefix exceeds the k‑digit range can be sent to a fallback shard, mirroring the overflow handling in the custom radix sort.

Examples

Example 1

Input

[170, 802, 24, 45, 66, 75, 90, 2]

Output

[2, 24, 45, 66, 75, 90, 170, 802]

Explanation: Step-by-step: 1. Initialize the custom radix sort with the given array and customBase. 2. Iterate over each digit position (from least significant to most significant) up to k digits. 3. For each digit position, group the numbers based on the digit at that position. 4. Sort the groups in ascending order. 5. Update the array with the sorted groups. 6. Repeat steps 2-5 until all digit positions have been processed. 7. If a number cannot be represented in the customBase within k digits, it remains at its original position.

Example 2

Input

[1000, 789, 56, 24, 23, 9, 7, 1]

Output

[1, 7, 9, 23, 24, 56, 789, 1000]

Constraints

1 <= customBase <= 16
1 <= k <= 10
1 <= array length <= 1000
0 <= array elements <= 10^6

Optimal Approach & Strategy

Perform k passes of stable counting sort on the integer array using digit extraction in the custom base, while pre‑filtering overflow numbers into a stable tail segment.

Brute Force Approach

Convert every integer to the custom base, truncate or pad to k digits, then sort the resulting strings with a standard O(n log n) comparator, handling overflow numbers separately.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n · k + n)

function customRadixSort(nums, customBase, k) {
   if (nums.length === 0) return nums;
   let max = Math.max(...nums);
   let exp = 1;
   while (Math.floor(max / exp) > 0 && k > 0) {
       let buckets = Array(customBase).fill(0).map(() => []);
       for (let num of nums) {
           let digit = Math.floor((num / exp) % customBase);
           buckets[digit].push(num);
       }
       nums = [].concat(...buckets);
       exp *= customBase;
       k--;
   }
   return nums;
}

class Solution {
public:
   vector<int> customRadixSort(vector<int>& nums, int customBase, int k) {
       if (nums.empty()) return nums;
       int max = *max_element(nums.begin(), nums.end());
       int exp = 1;
       while (max / exp > 0 && k > 0) {
           vector<vector<int>> buckets(customBase);
           for (int num : nums) {
               int digit = (num / exp) % customBase;
               buckets[digit].push_back(num);
           }
           nums.clear();
           for (auto& bucket : buckets) {
               nums.insert(nums.end(), bucket.begin(), bucket.end());
           }
           exp *= customBase;
           k--;
       }
       return nums;
   }
};

class Solution {
   public int[] customRadixSort(int[] nums, int customBase, int k) {
       if (nums.length == 0) return nums;
       int max = Arrays.stream(nums).max().getAsInt();
       int exp = 1;
       while (max / exp > 0 && k > 0) {
           int[][] buckets = new int[customBase][];
           for (int num : nums) {
               int digit = (num / exp) % customBase;
               buckets[digit] = Arrays.copyOf(buckets[digit], buckets[digit].length + 1);
               buckets[digit][buckets[digit].length - 1] = num;
           }
           nums = new int[buckets.length];
           int index = 0;
           for (int[] bucket : buckets) {
               for (int num : bucket) {
                   nums[index++] = num;
               }
           }
           exp *= customBase;
           k--;
       }
       return nums;
   }
}

def custom_radix_sort(nums, custom_base, k):
   if not nums:
       return nums
   max_num = max(nums)
   exp = 1
   while max_num // exp > 0 and k > 0:
       buckets = [[] for _ in range(custom_base)]
       for num in nums:
           digit = (num // exp) % custom_base
           buckets[digit].append(num)
       nums = [num for bucket in buckets for num in bucket]
       exp *= custom_base
       k -= 1
   return nums

function customRadixSort(nums, customBase, k) {
   if (nums.length === 0) return nums;
   let max = Math.max(...nums);
   let exp = 1;
   while (Math.floor(max / exp) > 0 && k > 0) {
       let buckets = Array(customBase).fill(0).map(() => []);
       for (let num of nums) {
           let digit = Math.floor((num / exp) % customBase);
           buckets[digit].push(num);
       }
       nums = [].concat(...buckets);
       exp *= customBase;
       k--;
   }
   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.

Custom Digit Sorting Solution

Problem Statement

Input

Output

Input

Output

Constraints

More Sorting

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Custom Digit 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