Ordinal Digit Sorting — Problem Statement & Solution Guide
Problem Description
You are given an array of integers. For each integer, determine the highest frequency of any decimal digit in its absolute value. Sort the array in descending order according to this maximum digit frequency. If two numbers have the same maximum frequency, order those numbers by descending numeric value. The input consists of an integer n followed by n integers. The output should be the sorted array, space‑separated, on a single line.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Ordinal Digit Sorting"
WHY DOES IT MATTER?
Custom sorting based on derived metrics appears in many real‑world ranking systems (e.g., prioritising tasks by urgency and then by cost). Mastering the decorate‑sort‑undecorate pattern lets you keep the heavy computation out of the comparator, guaranteeing predictable performance.
OPTIMIZATION CHALLENGE
The key insight is to compute the expensive digit‑frequency metric exactly once per element and store it, turning a potentially O(n · log n · d) comparator into an O(1) comparison. This reduces both time and constant‑factor overhead dramatically.
REAL-WORLD CONNECTION
Think of a load balancer that first groups requests by the most frequent error code they generate, then within each group serves the highest‑value customers first. The grouping step is analogous to computing the digit frequency, and the final ordering mirrors the custom sort.
When you see a sorting problem that depends on a non‑trivial property of each element, immediately think of pairing each element with its property in a lightweight struct or tuple, sort the structs, and then extract the original values.
COMPLEXITY AT A GLANCE
O(n log n + n·d)O(n)Core Theory — Why This Approach?
The problem reduces to a two‑step transformation followed by a custom sort. First, each integer is mapped to a key consisting of two components: (1) the highest occurrence count of any decimal digit in the absolute value of the number, and (2) the numeric value itself. Computing the digit frequency is a linear scan over the string representation or repeated modulo‑10 operations, which runs in O(d) where d is the number of digits (at most 19 for 64‑bit integers). Second, the array is sorted in descending order using the composite key, prioritising the frequency component and breaking ties with the numeric value. A naive solution would recompute the digit frequencies during every comparison in the sort, leading to O(n · log n · d) time, which is unnecessary overhead. By pre‑computing the keys once and storing them alongside the original numbers, the sort becomes a standard O(n log n) operation with constant‑time key comparisons. This separation of concerns follows the optimal paradigm of "decorate‑sort‑undecorate" (also known as Schwartzian transform), which is essential for any problem where a costly per‑element metric determines ordering.
Interview Questions on This Problem
Q1How would you modify the solution if the sorting order for the numeric tie‑breaker had to be ascending instead of descending?
Compute the same frequency key, but during the sort use a comparator that orders by frequency descending and, when frequencies are equal, orders the original numbers ascending. The rest of the algorithm (digit counting) stays unchanged.
Q2What is the time complexity if the input numbers can have up to 10^5 digits each (e.g., arbitrary‑precision integers)?
Digit counting becomes O(D) per number where D is the number of digits, so the overall complexity is O(∑D_i + n log n). In the worst case with each number having 10^5 digits, this is O(n·10^5 + n log n), dominated by the digit‑scanning phase.
Q3Explain how you could parallelise the preprocessing step on a multi‑core system.
The digit‑frequency computation for each element is independent, so you can partition the array into chunks, let each thread compute the (frequency, value) pair for its chunk, and store the results in a shared structure. After all threads finish, perform a single parallel or sequential sort on the aggregated key‑value pairs.
Examples
Input
5 121 33 444 12 7
Output
444 121 33 12 7
Explanation: Maximum digit frequencies: 121→2, 33→2, 444→3, 12→1, 7→1. Sorting by frequency gives 444 first. The two numbers with frequency 2 are 121 and 33; 121 is larger, so it comes next. Finally 12 and 7 both have frequency 1; 12 is larger, so it follows 7. Result: 444 121 33 12 7.
Input
4 -22 0 101 5555
Output
5555 101 -22 0
Explanation: Absolute values: 22, 0, 101, 5555. Frequencies: 22→2, 0→1, 101→2, 5555→4. Highest frequency is 4 for 5555. The remaining two numbers with frequency 2 are 101 and -22; 101 is larger, so it comes next. Finally 0. Result: 5555 101 -22 0.
Input
6 123 321 111 222 333 444
Output
444 333 222 111 321 123
Explanation: Frequencies: 123→1, 321→1, 111→3, 222→3, 333→3, 444→3. All numbers with frequency 3 are sorted by descending value: 444, 333, 222, 111. The two with frequency 1 are 321 and 123, sorted as 321, 123. Result: 444 333 222 111 321 123.
Constraints
- 1 <= n <= 100000
- -1000000000 <= nums[i] <= 1000000000
Optimal Approach & Strategy
Pre‑compute each number's max digit frequency once, store it with the number, and sort using these pre‑computed keys, achieving O(n log n) time.
Brute Force Approach
Repeatedly compare two numbers by recomputing their digit frequencies during each comparison, leading to O(n log n · d) time.
Verified Code Solutions
function solution(nums) {
return nums.sort((a, b) => {
const freqA = getFrequency(a);
const freqB = getFrequency(b);
if (freqA === freqB) {
return b - a;
} else {
return freqB - freqA;
}
});
}
function getFrequency(num) {
const str = num.toString();
const freq = {};
for (let i = 0; i < str.length; i++) {
const digit = str[i];
if (!freq[digit]) {
freq[digit] = 1;
} else {
freq[digit]++;
}
}
return Math.max(...Object.values(freq));
}class Solution {
public:
vector<int> solution(vector<int>& nums) {
sort(nums.begin(), nums.end(), [](int a, int b) {
int freqA = getFrequency(a);
int freqB = getFrequency(b);
if (freqA == freqB) {
return b < a;
} else {
return freqB > freqA;
}
});
return nums;
}
int getFrequency(int num) {
string str = to_string(num);
int freq[10] = {0};
for (char c : str) {
freq[c - '0']++;
}
int max = 0;
for (int i : freq) {
max = std::max(max, i);
}
return max;
}
};import java.util.Arrays;
class Solution {
public int[] solution(int[] nums) {
Arrays.sort(nums, (a, b) -> {
int freqA = getFrequency(a);
int freqB = getFrequency(b);
if (freqA == freqB) {
return b - a;
} else {
return freqB - freqA;
}
});
return nums;
}
private int getFrequency(int num) {
String str = String.valueOf(num);
int[] freq = new int[10];
for (char c : str.toCharArray()) {
freq[c - '0']++;
}
int max = 0;
for (int i : freq) {
max = Math.max(max, i);
}
return max;
}
}def solution(nums):
def get_frequency(num):
freq = {}
for digit in str(num):
if digit not in freq:
freq[digit] = 1
else:
freq[digit] += 1
return max(freq.values())
return sorted(nums, key=lambda x: (-get_frequency(x), -x))function solution(nums) {
return nums.sort((a, b) => {
const freqA = getFrequency(a);
const freqB = getFrequency(b);
if (freqA === freqB) {
return b - a;
} else {
return freqB - freqA;
}
});
}
function getFrequency(num) {
const str = num.toString();
const freq = {};
for (let i = 0; i < str.length; i++) {
const digit = str[i];
if (!freq[digit]) {
freq[digit] = 1;
} else {
freq[digit]++;
}
}
return Math.max(...Object.values(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.