Least Significant Digit Frequency Sort — Problem Statement & Solution Guide

SortingMediumCounting/Radix Sort

TimeO(n)

SpaceO(n)

Problem Description

Given an array of non-negative integers, sort the array based on the frequency of the least significant digit of each number in the entire array. If two numbers have the same frequency of the least significant digit, sort them based on the value of the least significant digit itself.

DSA Pattern Breakdown

"Least Significant Digit Frequency Sort"

medium

WHY DOES IT MATTER?

Frequency‑based sorting is a recurring pattern in problems where the importance of an element is derived from its occurrence count rather than its intrinsic value. Mastering this pattern equips engineers to handle custom ranking, load‑balancing decisions, and cache eviction policies where frequency dictates priority.

OPTIMIZATION CHALLENGE

The key insight is recognizing that the LSD domain is only ten values, allowing us to replace a generic O(n log n) sort with a linear‑time counting‑sort that first aggregates frequencies, then orders the ten buckets by a composite key. This reduces both time and auxiliary space dramatically.

REAL-WORLD CONNECTION

Think of a distributed logging system that routes logs to shards based on the frequency of error codes (the LSD). Rare error codes are sent to a high‑priority shard for faster investigation, while common codes go to a bulk‑processing shard. The same bucket‑by‑frequency logic determines the routing order.

During an interview, compute the digit frequencies first and store numbers in per‑digit buckets. Then sort the ten digit keys (a trivial step) and concatenate buckets. This approach is easy to code, avoids hidden O(n log n) costs, and demonstrates a clear, optimal thought process.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(n)

Core Theory — Why This Approach?

The core of this problem lies in frequency‑based ordering, a classic example of a counting‑sort variant. By focusing on the least significant digit (LSD) – the value of num mod 10 – we reduce the universe of keys to just ten possibilities (0‑9). A naïve solution would compare every pair of numbers, leading to O(n²) time, which quickly becomes infeasible for large n (e.g., n = 10⁶). Instead, we first tally how many times each digit appears, which is an O(n) pass, and then use those tallies to drive a deterministic ordering.

Once the frequencies are known, the problem transforms into sorting a small set of keys (the ten digits) by a composite key: (frequency, digit value). Because the key space is constant‑size, we can sort it in O(1) time (effectively O(10 log 10)). Finally, we emit the original numbers grouped by their LSD according to this sorted key order. This yields an overall linear‑time algorithm that leverages the optimal paradigm of counting‑sort combined with a tiny custom comparator, avoiding the overhead of generic comparison‑based sorts.

The optimal approach also demonstrates the power of “bucket‑by‑key then reorder” techniques, which are especially useful when the key domain is bounded. By exploiting the bounded digit range, we achieve O(n) time and O(n) auxiliary space, a dramatic improvement over the quadratic brute‑force method and even over an O(n log n) comparison sort, making the solution scalable for massive input sizes.

Interview Questions on This Problem

Q1How would you modify the solution if the sorting criterion changed from the least significant digit to the most significant digit of each number?

Count frequencies of the most significant digit (MSD) by extracting the leading digit (e.g., using while loops or logarithms). Then apply the same bucket‑by‑frequency technique: sort the ten possible MSD values by (frequency, digit) and concatenate numbers whose MSD matches each bucket, preserving stability. The overall complexity remains O(n) because the key space is still constant.

Q2Can you solve the problem in O(n) time without using any built‑in sort functions? Explain the steps.

Yes. First, traverse the array once to compute freq[0..9] for each LSD. Next, create an array of digit buckets (vector<int> bucket[10]) and push each number into bucket[num%10] preserving input order. Then, build a list of the ten digits and sort this tiny list by (freq[d], d) using any O(1) sort (e.g., insertion sort on 10 elements). Finally, iterate over the sorted digit list and output all numbers from the corresponding bucket. This uses only linear passes and constant‑size sorting, achieving O(n) time and O(n) extra space.

Q3Why is a counting‑sort style solution preferable to a generic quicksort when the key domain is limited, and what pitfalls should you watch for?

Counting sort exploits the bounded key range to avoid the O(n log n) comparison overhead, delivering linear time. It also guarantees stability, which is crucial when secondary ordering (e.g., original order) matters. Pitfalls include forgetting to handle numbers with the same LSD but different frequencies correctly, and ensuring that the frequency‑based ordering of the digit buckets is computed after the frequency count, not before.

Examples

Example 1

Input

[127, 624, 354, 413, 256]

Output

[127, 624, 354, 413, 256]

Explanation: Step 1: Calculate the frequency of the least significant digit for each number in the array. The frequency of 7 is 1, 6 is 1, 4 is 2, and 3 is 1. Step 2: Sort the numbers based on the frequency of the least significant digit in descending order. The numbers with the least significant digit 4 should come first, followed by the numbers with the least significant digit 7, and then the numbers with the least significant digit 6. Step 3: Sort the numbers with the same frequency based on the least significant digit itself in ascending order. The numbers with the least significant digit 4 should come first, followed by the numbers with the least significant digit 7, and then the numbers with the least significant digit 6. Step 4: The final sorted array is [127, 624, 354, 413, 256].

Example 2

Input

[100, 100, 201, 200]

Output

[100, 100, 200, 201]

Explanation: Step 1: Calculate the frequency of the least significant digit for each number in the array. The frequency of 0 is 3 and 1 is 1. Step 2: Sort the numbers based on the frequency of the least significant digit in descending order. The numbers with the least significant digit 0 should come first, followed by the numbers with the least significant digit 1. Step 3: Sort the numbers with the same frequency based on the least significant digit itself in ascending order. The numbers with the least significant digit 0 should come first, followed by the numbers with the least significant digit 1. Step 4: The final sorted array is [100, 100, 200, 201].

Constraints

0 <= array length <= 10^5
0 <= array elements <= 10^6

Optimal Approach & Strategy

Count LSD frequencies in O(n), bucket numbers by LSD, sort the ten digit keys by (frequency, digit) in O(1), then concatenate buckets for O(n) total time.

Brute Force Approach

For each pair of numbers, compute their LSD frequencies and compare them, resulting in O(n²) time.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

function solution(nums) {
   const map = new Map();
   for (let num of nums) {
       let digit = num % 10;
       map.set(digit, (map.get(digit) || 0) + 1);
   }
   nums.sort((a, b) => {
       let digitA = a % 10;
       let digitB = b % 10;
       let freqA = map.get(digitA);
       let freqB = map.get(digitB);
       if (freqA !== freqB) {
           return freqB - freqA;
       } else {
           return digitA - digitB;
       }
   });
   return nums;
}

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

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

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

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

Problem Statement

Input

Output

Input

Output

Constraints

More Sorting

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

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