Digit Distribution Sorting 2 — Problem Statement & Solution Guide

SortingEasyCounting/Radix Sort

TimeO(N · D + N log N)

SpaceO(N)

Problem Description

Given a list of integers, sort them based on the frequency of each digit (0-9) in the absolute value of each number. The frequency of each digit is counted, and numbers are sorted first by the highest frequency of any single digit and then by their numerical value in ascending order.

DSA Pattern Breakdown

"Digit Distribution Sorting 2"

easy

WHY DOES IT MATTER?

Transform‑then‑sort is a fundamental pattern when custom ordering depends on costly per‑element metrics. By extracting a lightweight key first, you decouple expensive computation from the O(N log N) sorting kernel, ensuring scalability.

OPTIMIZATION CHALLENGE

The key insight is recognizing that digit frequencies are bounded to ten categories, allowing a constant‑time histogram per number and enabling the use of a simple pair (maxFreq, value) as the sort key, which eliminates repeated digit scans inside the comparator.

REAL-WORLD CONNECTION

Think of a distributed log‑aggregation system that tags each log entry with a severity score computed from its content. The system first annotates each entry (expensive parsing) and then routes logs based on the pre‑computed score, similar to pre‑computing digit frequencies before sorting.

When implementing, compute the max frequency in a single pass over the digits, store it alongside the original number in a struct or tuple, and rely on the language's stable sort to respect the secondary numeric order without extra code.

COMPLEXITY AT A GLANCE

⏱ Time:O(N · D + N log N)

💾 Space:O(N)

Core Theory — Why This Approach?

The problem requires a custom comparator that ranks integers by the highest occurrence of any single digit in their absolute decimal representation. A naive solution would recompute digit frequencies during each comparison, leading to O(N · log N · D) time where D is the number of digits, which quickly becomes prohibitive for large N (e.g., N = 10⁶). The optimal paradigm separates the expensive digit‑frequency analysis from the sorting phase: first, in a linear pass, compute for every element the maximum digit count (a constant‑size 10‑bucket histogram), storing this as a key alongside the original value. Then a single stable sort using a comparator that orders by descending max‑frequency and ascending numeric value yields O(N log N) overall, with the digit counting contributing only O(N · D) which is linear in the input size. This two‑step approach leverages the fact that digit frequencies are bounded (10 possible digits) and can be pre‑computed, turning a potentially quadratic comparison cost into a linear preprocessing step.

The optimal solution also highlights a broader algorithmic pattern: transform the data into a richer key space before sorting, allowing the sort to operate on simple scalar values. By reducing each number to a pair (maxFreq, value), we avoid repeated work inside the comparator and exploit the highly optimized sort implementations provided by standard libraries. This technique is especially powerful when the custom ordering depends on expensive per‑element calculations, a common scenario in interview problems that test both analytical thinking and practical coding efficiency.

Interview Questions on This Problem

Q1How would you modify the solution if the sorting criteria required the sum of digit frequencies instead of the maximum frequency?

Compute the sum of digit counts for each number during the preprocessing pass (still O(D) per number) and store it as the primary key. Then sort by descending sum and ascending value. The overall complexity remains O(N log N + N · D).

Q2Can you achieve linear‑time sorting for this problem if the range of numbers is bounded (e.g., all numbers fit in 32‑bit signed int)?

Yes. Since maxFreq can only range from 1 to 10 (a digit can appear at most the number of digits, but the maximum possible is limited by the number of digits, which for 32‑bit ints is ≤10), we can bucket the numbers by maxFreq (10 buckets) and then apply counting sort within each bucket, achieving O(N + K) time where K is the number of buckets (constant).

Q3Why is it important to use the absolute value of numbers when counting digit frequencies, and how would you handle negative numbers in your implementation?

Digit frequencies are defined on the decimal representation without the sign, so using absolute value ensures consistency (e.g., -112 and 112 have the same digit distribution). In code, take Math.abs(num) before extracting digits; for Integer.MIN_VALUE, cast to long before abs to avoid overflow.

Examples

Example 1

Input

[1011, 123, 1213, 456, 789]

Output

[1011, 123, 1213, 456, 789]

Explanation: Step 1: Count the frequency of each digit in each number. For 1011, the frequency of 1 is 2, and the frequency of 0 is 1. For 123, the frequency of 1 is 1, and the frequency of 2 and 3 are both 1. Step 2: Find the maximum frequency of any single digit in each number. For 1011, the maximum frequency is 2. For 123, the maximum frequency is 1. Step 3: Sort the numbers based on the maximum frequency of any single digit and then by their numerical value in ascending order. Since 1011 has a maximum frequency of 2, which is greater than 1, it comes first. Then comes 123, which has a maximum frequency of 1.

Example 2

Input

[333, 222, 555, 444, 111]

Output

[333, 222, 555, 444, 111]

Explanation: Step 1: Count the frequency of each digit in each number. For 333, the frequency of 3 is 3. For 222, the frequency of 2 is 3. For 555, the frequency of 5 is 3. For 444, the frequency of 4 is 3. For 111, the frequency of 1 is 3. Step 2: Find the maximum frequency of any single digit in each number. For 333, 222, 555, 444, and 111, the maximum frequency is 3. Step 3: Sort the numbers based on the maximum frequency of any single digit and then by their numerical value in ascending order. Since all numbers have the same maximum frequency of 3, they are sorted by their numerical value in ascending order.

Constraints

1 <= N <= 10^5, where N is the number of elements in the input list.
0 <= num <= 10^6, for any num in the input list.

Optimal Approach & Strategy

Precompute the maximum digit frequency for each number in O(N · D) time, store it, and then sort using a comparator that accesses this precomputed key, achieving O(N log N) overall.

Brute Force Approach

Repeatedly compare numbers by recomputing digit frequencies inside the comparator, leading to O(N · log N · D) time.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(N · D + N log N)

function solution(nums) {
   let maxFreq = 0;
   let sortedNums = [...nums];
   sortedNums.sort((a, b) => {
      let freqA = getFrequency(a);
      let freqB = getFrequency(b);
      if (Math.max(...freqA) !== Math.max(...freqB)) {
         return Math.max(...freqB) - Math.max(...freqA);
      } else {
         return a - b;
      }
   });
   return sortedNums;
}

function getFrequency(num) {
   let freq = new Array(10).fill(0);
   for (let digit of num.toString()) {
      freq[digit] += 1;
   }
   return freq;
}

class Solution {
public:
   vector<int> solution(vector<int>& nums) {
      vector<int> maxFreq(10, 0);
      sort(nums.begin(), nums.end(), [](int a, int b) {
         int freqA[10] = {0};
         int freqB[10] = {0};
         for (char digit : to_string(a).c_str()) {
            freqA[digit - '0'] += 1;
         }
         for (char digit : to_string(b).c_str()) {
            freqB[digit - '0'] += 1;
         }
         if (max_element(freqB, freqB + 10) - freqB != max_element(freqA, freqA + 10) - freqA) {
            return *max_element(freqB, freqB + 10) - *max_element(freqA, freqA + 10);
         } else {
            return a - b;
         }
      });
      return nums;
   }
}

class Solution {
   public int[] solution(int[] nums) {
      int[] maxFreq = new int[10];
      Arrays.sort(nums, (a, b) -> {
         int[] freqA = getFrequency(a);
         int[] freqB = getFrequency(b);
         if (Arrays.stream(freqB).max().getAsInt() != Arrays.stream(freqA).max().getAsInt()) {
            return Arrays.stream(freqB).max().getAsInt() - Arrays.stream(freqA).max().getAsInt();
         } else {
            return a - b;
         }
      });
      return nums;
   }

   public int[] getFrequency(int num) {
      int[] freq = new int[10];
      for (char digit : String.valueOf(num).toCharArray()) {
         freq[digit - '0'] += 1;
      }
      return freq;
   }
}

def solution(nums):
   max_freq = 0
   sorted_nums = sorted(nums, key=lambda x: (max(map(int, str(x))), x))
   return sorted_nums

def get_frequency(num):
   freq = [0] * 10
   for digit in str(num):
      freq[int(digit)] += 1
   return freq

function solution(nums) {
   let maxFreq = 0;
   let sortedNums = [...nums];
   sortedNums.sort((a, b) => {
      let freqA = getFrequency(a);
      let freqB = getFrequency(b);
      if (Math.max(...freqA) !== Math.max(...freqB)) {
         return Math.max(...freqB) - Math.max(...freqA);
      } else {
         return a - b;
      }
   });
   return sortedNums;
}

function getFrequency(num) {
   let freq = new Array(10).fill(0);
   for (let digit of num.toString()) {
      freq[digit] += 1;
   }
   return freq;
}

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 2 Solution

Problem Statement

Input

Output

Input

Output

Constraints

More Sorting

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Digit Distribution Sorting 2 — 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