Least Significant Digit Frequency Sort 2 — Problem Statement & Solution Guide

SortingEasyCounting/Radix Sort

TimeO(n)

SpaceO(n)

Problem Description

You are given an array of non-negative integers. Your task is to sort this array using a specific two-tiered stability-preserving logic. The primary sorting criterion is the frequency of the least significant digit (LSD) of each number, calculated across the entire input array. Numbers with a lower LSD frequency should appear before those with a higher frequency. The secondary sorting criterion is the value of the LSD itself, arranged in ascending order. If two numbers share the same LSD frequency and the same LSD value, their relative order from the original input must be preserved (stable sort). Return the sorted array.

DSA Pattern Breakdown

"Least Significant Digit Frequency Sort 2"

easy

WHY DOES IT MATTER?

Frequency‑based bucket sorting is a fundamental pattern for problems where ordering depends on how often a property occurs. Recognizing the bounded nature of the property (here, a digit) lets you replace generic comparison‑based sorts with linear‑time bucket techniques, dramatically improving performance on large inputs.

OPTIMIZATION CHALLENGE

The key insight is decoupling frequency calculation from sorting: compute a global frequency map in O(n) once, then use that map as a constant‑time lookup during a single stable pass that groups elements by frequency. This eliminates repeated digit extraction and avoids O(n log n) sorting overhead.

REAL-WORLD CONNECTION

Think of a distributed logging system that routes messages to servers based on the frequency of a particular tag. Rare tags are processed first to reduce contention, while preserving the arrival order of messages with the same tag – analogous to sorting by LSD frequency while keeping stability.

When implementing, store the original index alongside each value or simply push values into frequency buckets in input order; this automatically guarantees stability without extra bookkeeping.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(n)

Core Theory — Why This Approach?

The problem hinges on a two‑level stable ordering: first by how often the least‑significant digit (LSD) appears in the whole array, then by the original input order for numbers sharing the same frequency. A naïve solution would recompute the LSD frequency for each element during sorting, leading to O(n log n) or even O(n²) time depending on the implementation, which is unnecessary because the LSD domain is tiny (0‑9). By pre‑computing a frequency table of size ten in a single linear pass, we reduce the dominant work to O(n). The second insight is to preserve stability without an extra O(n log n) sort; using counting‑style buckets keyed by frequency (which can range from 0 to n) or a stable sort with a composite key (frequency, original index) yields a linear‑time, stable arrangement. This aligns with the optimal paradigm of "frequency‑based bucket sort" – a classic linear‑time technique when the key space is bounded or can be mapped to a small range.

Interview Questions on This Problem

Q1How would you sort an array of integers by the frequency of their least‑significant digit while keeping the original order for ties?

First, scan the array once to count how many times each digit 0‑9 appears as the LSD. Then, iterate the original array and place each element into a bucket corresponding to its LSD frequency; because we insert elements in input order, the buckets are naturally stable. Finally, concatenate the buckets from lowest frequency to highest to obtain the sorted array.

Q2Why is a stable sort required for this problem, and what could go wrong if you use an unstable sort like quicksort with a custom comparator?

Stability guarantees that elements with equal LSD frequency retain their original relative order, which is part of the problem specification. An unstable sort could reorder equal‑frequency elements arbitrarily, causing the output to violate the required tie‑breaking rule and leading to wrong answers on test cases that check order preservation.

Q3Can you achieve O(n) time and O(n) auxiliary space for this task? Explain the data structures you would use.

Yes. Use an array of size 10 to store LSD frequencies (O(1) space) and another array of vectors (or lists) of size n+1 to bucket elements by their frequency (O(n) space). After filling the buckets in a single pass, iterate frequencies from 0 to n and output the concatenated buckets, achieving O(n) time overall.

Examples

Example 1

Input

nums = [12, 34, 56, 78, 90]

Output

[90, 12, 34, 56, 78]

Explanation: First, determine the LSD for each number: 12->2, 34->4, 56->6, 78->8, 90->0. Next, count the frequency of each LSD in the array: 0 appears 1 time, 2 appears 1 time, 4 appears 1 time, 6 appears 1 time, 8 appears 1 time. All numbers have an LSD frequency of 1. Therefore, the primary sort key is identical for all. We proceed to the secondary sort key, which is the LSD value in ascending order. Sorting by LSD: 0 (from 90), 2 (from 12), 4 (from 34), 6 (from 56), 8 (from 78). The final order is [90, 12, 34, 56, 78].

Example 2

Input

nums = [11, 22, 33, 44, 55]

Output

[11, 22, 33, 44, 55]

Explanation: LSDs are: 1, 2, 3, 4, 5. Frequency of each LSD is 1. Since all frequencies are equal, we sort by the LSD value in ascending order. The LSDs are already in ascending order (1, 2, 3, 4, 5). Thus, the original order is preserved: [11, 22, 33, 44, 55].

Example 3

Input

nums = [10, 20, 30, 40, 50]

Output

[10, 20, 30, 40, 50]

Explanation: LSDs are: 0, 0, 0, 0, 0. The frequency of LSD 0 is 5. All numbers have the same primary key (frequency 5) and the same secondary key (LSD 0). Since the sort is stable, the original relative order is maintained: [10, 20, 30, 40, 50].

Example 4

Input

nums = [12, 22, 32, 41, 51]

Output

[41, 51, 12, 22, 32]

Explanation: LSDs are: 2, 2, 2, 1, 1. Frequency of LSD 2 is 3. Frequency of LSD 1 is 2. Primary sort by frequency ascending: Numbers with LSD 1 (freq 2) come before numbers with LSD 2 (freq 3). Group 1 (LSD 1): [41, 51]. Group 2 (LSD 2): [12, 22, 32]. Within each group, secondary sort by LSD value ascending. Since all in Group 1 have LSD 1 and all in Group 2 have LSD 2, the order within groups is preserved due to stability. Final result: [41, 51, 12, 22, 32].

Constraints

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

Optimal Approach & Strategy

Pre‑compute LSD frequencies in O(n), then perform a single stable bucket pass based on those frequencies, achieving O(n) time overall.

Brute Force Approach

For each element, recompute the LSD frequency across the whole array and sort using a comparator that looks up this count, leading to O(n²) time.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

function solution(nums) {
   let map = new Map();
   for (let num of nums) {
       let lsd = num % 10;
       map.set(lsd, (map.get(lsd) || 0) + 1);
   }
   nums.sort((a, b) => {
       let lsdA = a % 10;
       let lsdB = b % 10;
       if (map.get(lsdA) !== map.get(lsdB)) {
           return map.get(lsdA) - map.get(lsdB);
       } else {
           return lsdA - lsdB;
       }
   });
   return nums;
}

class Solution {
   public:
   vector<int> solution(vector<int>& nums) {
       map<int, int> map;
       for (int num : nums) {
           int lsd = num % 10;
           map[lsd] = map[lsd] + 1;
       }
       sort(nums.begin(), nums.end(), [](int a, int b) {
           int lsdA = a % 10;
           int lsdB = b % 10;
           if (map[lsdA] != map[lsdB]) {
               return map[lsdA] - map[lsdB];
           } else {
               return lsdA - lsdB;
           }
       });
       return nums;
   }
};

class Solution {
   public int[] solution(int[] nums) {
       Map<Integer, Integer> map = new HashMap<>();
       for (int num : nums) {
           int lsd = num % 10;
           map.put(lsd, map.getOrDefault(lsd, 0) + 1);
       }
       Arrays.sort(nums, (a, b) -> {
           int lsdA = a % 10;
           int lsdB = b % 10;
           if (map.get(lsdA) != map.get(lsdB)) {
               return map.get(lsdA) - map.get(lsdB);
           } else {
               return lsdA - lsdB;
           }
       });
       return nums;
   }
}

def solution(nums):
   map = {}
   for num in nums:
       lsd = num % 10
       map[lsd] = map.get(lsd, 0) + 1
   nums.sort(key=lambda x: (x % 10, x % 10))
   return nums

function solution(nums) {
   let map = new Map();
   for (let num of nums) {
       let lsd = num % 10;
       map.set(lsd, (map.get(lsd) || 0) + 1);
   }
   nums.sort((a, b) => {
       let lsdA = a % 10;
       let lsdB = b % 10;
       if (map.get(lsdA) !== map.get(lsdB)) {
           return map.get(lsdA) - map.get(lsdB);
       } else {
           return lsdA - lsdB;
       }
   });
   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.

Least Significant Digit Frequency Sort 2 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

Least Significant Digit Frequency Sort 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