Digit Frequency Sorting — Problem Statement & Solution Guide

SortingEasyCounting/Radix Sort

TimeO(N)

SpaceO(K)

Problem Description

You are given an array of non-negative integers. Your task is to reorder the array such that the elements are sorted in ascending order based on the count of decimal digits in each number. For instance, single-digit numbers (0-9) should appear before two-digit numbers (10-99), which should appear before three-digit numbers, and so on.

A critical requirement is stability: if two numbers possess the same number of digits, their relative order from the original input array must be preserved in the final output. This implies that you should not sort by the numeric value of the integers themselves, but strictly by their digit length, maintaining the original sequence for ties.

Return the modified array after applying this specific sorting logic. The solution should efficiently handle large inputs by leveraging counting or radix sort principles rather than general-purpose comparison-based sorting algorithms.

DSA Pattern Breakdown

"Digit Frequency Sorting"

easy

WHY DOES IT MATTER?

Digit‑frequency sorting is a concrete example of sorting by a derived attribute rather than the raw value. Mastering this pattern teaches you how to decouple the comparison key from the data, a skill that appears in many real‑world scenarios such as priority queues, custom ranking, and multi‑criteria ordering.

OPTIMIZATION CHALLENGE

The key insight is recognizing that digit count has a tiny, fixed domain, allowing a linear‑time bucket (counting sort) instead of a generic O(N log N) comparison sort. This reduces both time and the need for expensive per‑comparison digit counting.

REAL-WORLD CONNECTION

Think of log aggregation pipelines that group events by severity level (e.g., INFO, WARN, ERROR) before further processing. The severity acts like the digit count—an inexpensive, bounded attribute that determines processing order while preserving the original event sequence within each group.

When coding this in an interview, first write a helper to compute digit length (use a loop or pre‑computed thresholds). Then allocate a list of lists for buckets, iterate once to fill them, and finally flatten. This one‑pass bucket approach is both fast and trivially stable.

COMPLEXITY AT A GLANCE

⏱ Time:O(N)

💾 Space:O(K)

Core Theory — Why This Approach?

The task reduces to a stable sort where the key is the number of decimal digits of each integer. A naive approach would compare every pair of elements and count digits on the fly, leading to O(N^2) time for large N. The optimal paradigm leverages the fact that digit count is bounded by a small constant (max 10 for 32‑bit ints, 19 for 64‑bit). By first computing the digit length for each element in O(1) time, we can bucket the numbers by length and then concatenate the buckets preserving original order – a classic counting‑sort technique that runs in linear time. If the digit range is larger or unknown, a stable sort with a custom key (e.g., std::stable_sort in C++ or Python's sorted with key=lambda x: len(str(x))) gives O(N log N) time while guaranteeing stability, which is still far superior to the quadratic brute force.

Interview Questions on This Problem

Q1How would you sort an array of non‑negative integers by the number of digits while preserving the original relative order of equal‑digit numbers?

Compute the digit count for each element, then perform a stable sort using that count as the key. In practice, a counting‑sort style bucket array indexed by digit length (0‑19 for 64‑bit) works in O(N) time and O(K) extra space, where K is the maximum digit length.

Q2Why is stability important in this problem, and how does it affect your choice of sorting algorithm?

Stability ensures that numbers with the same digit count remain in their original order, which the problem explicitly requires. Therefore, we must use a stable sorting method—either a language‑provided stable sort (e.g., Python's sorted, Java's stable sort) or a manual bucket concatenation that respects insertion order.

Q3If the input range includes numbers up to 10^18, what is the maximum number of buckets needed for a counting‑sort solution, and what is the overall time complexity?

10^18 has 19 decimal digits, so we need 20 buckets (0‑19). The algorithm runs in O(N) time to distribute elements plus O(N) to collect them, yielding overall O(N) time and O(20) = O(1) auxiliary space.

Examples

Example 1

Input

nums = [12, 5, 345, 9, 100, 7]

Output

[5, 9, 7, 12, 100, 345]

Explanation: First, determine the digit count for each element: 12 (2 digits), 5 (1 digit), 345 (3 digits), 9 (1 digit), 100 (3 digits), 7 (1 digit). Group by digit count while preserving original order: 1-digit group is [5, 9, 7]; 2-digit group is [12]; 3-digit group is [345, 100]. Concatenating these groups in ascending order of digit count yields [5, 9, 7, 12, 100, 345].

Example 2

Input

nums = [1000, 99, 1, 10, 9999]

Output

[1, 99, 10, 1000, 9999]

Explanation: Digit counts: 1000 (4), 99 (2), 1 (1), 10 (2), 9999 (4). Grouping by count: 1-digit: [1]; 2-digit: [99, 10] (original order preserved); 4-digit: [1000, 9999] (original order preserved). Note that there are no 3-digit numbers. The final sorted array is [1, 99, 10, 1000, 9999].

Example 3

Input

nums = [0, 10, 1, 100, 11]

Output

[0, 1, 10, 11, 100]

Explanation: Digit counts: 0 (1), 10 (2), 1 (1), 100 (3), 11 (2). Grouping: 1-digit: [0, 1]; 2-digit: [10, 11]; 3-digit: [100]. The result is the concatenation of these groups: [0, 1, 10, 11, 100].

Example 4

Input

nums = [999, 1000, 99, 100]

Output

[99, 100, 999, 1000]

Explanation: Digit counts: 999 (3), 1000 (4), 99 (2), 100 (3). Grouping: 2-digit: [99]; 3-digit: [999, 100] (original order preserved); 4-digit: [1000]. The final array is [99, 999, 100, 1000].

Constraints

1 <= nums.length <= 10^5
0 <= nums[i] <= 10^9
The input array may contain duplicate values.

Optimal Approach & Strategy

Use a stable bucket (counting) sort keyed by digit length, which runs in O(N) time and O(K) extra space, where K is the maximum digit count.

Brute Force Approach

Compare every pair of numbers, count digits each time, and swap if the left has more digits than the right, resulting in O(N^2) time.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(N)

function solution(nums) {
   if (nums.length === 0) return nums;
   nums.sort((a, b) => {
       if (a < 0 || b < 0) return -1; // handle negative numbers
       const numDigitsA = Math.floor(Math.log10(Math.abs(a))) + 1;
       const numDigitsB = Math.floor(Math.log10(Math.abs(b))) + 1;
       if (numDigitsA !== numDigitsB) return numDigitsA - numDigitsB;
       return nums.indexOf(a) - nums.indexOf(b); // preserve original order
   });
   return nums;
}

class Solution {
   public:
       vector<int> solution(vector<int>& nums) {
           if (nums.size() == 0) return nums;
           sort(nums.begin(), nums.end(), [](int a, int b) {
               if (a < 0 || b < 0) return -1; // handle negative numbers
               int numDigitsA = to_string(abs(a)).size();
               int numDigitsB = to_string(abs(b)).size();
               if (numDigitsA != numDigitsB) return numDigitsA - numDigitsB;
               return distance(nums.begin(), find(nums.begin(), nums.end(), a)) - distance(nums.begin(), find(nums.begin(), nums.end(), b)); // preserve original order
           });
           return nums;
       }
   };

class Solution {
   public int[] solution(int[] nums) {
       if (nums.length == 0) return nums;
       Arrays.sort(nums, (a, b) -> {
           if (a < 0 || b < 0) return -1; // handle negative numbers
           int numDigitsA = (int) Math.log10(Math.abs(a)) + 1;
           int numDigitsB = (int) Math.log10(Math.abs(b)) + 1;
           if (numDigitsA != numDigitsB) return numDigitsA - numDigitsB;
           return Arrays.asList(nums).indexOf(a) - Arrays.asList(nums).indexOf(b); // preserve original order
       });
       return nums;
   }
}

def solution(nums):
   if not nums:
       return nums
   nums.sort(key=lambda x: (len(str(abs(x))), nums.index(x)))
   return nums

function solution(nums) {
   if (nums.length === 0) return nums;
   nums.sort((a, b) => {
       if (a < 0 || b < 0) return -1; // handle negative numbers
       const numDigitsA = Math.floor(Math.log10(Math.abs(a))) + 1;
       const numDigitsB = Math.floor(Math.log10(Math.abs(b))) + 1;
       if (numDigitsA !== numDigitsB) return numDigitsA - numDigitsB;
       return nums.indexOf(a) - nums.indexOf(b); // preserve original order
   });
   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 Frequency Sorting Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Sorting

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

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