If you are given a long string of numeric digits, like "50122", and asked to rearrange the digits to construct the smallest possible number, the standard sorting approach (O(N Log N)) is to sort characters. However, since the digit range is very small (only digits 0 to 9), we can optimize this to O(N) using **Counting Sort**.

Visualizing digit count sorting
Real-World Analogy: Numbered Tile Organizers

Imagine you have a messy pile of numbered toy tiles (digits). You want to align them to make the smallest number possible.

Instead of comparing tiles, you place 10 plastic trays labeled **0 to 9** on the table. You pick up each tile from the pile and drop it in its matching tray:

  • All `0` tiles go to tray 0, all `1` tiles to tray 1, and so on.

To write down the smallest number, you simply look at the trays from left to right (0 first, then 1, then 2...) and lay out all the tiles from each tray in order! You get "01225".

Step-by-Step Logic Trace

  1. Set up a bucket array of size 9 (or 10) to hold digit counts: int[] arr = new int[10];.
  2. Convert the input number string to a character array.
  3. For each character, parse it as an integer index and increment the count in your bucket array: arr[digit]++.
  4. Set up a StringBuilder.
  5. Loop from index 0 to 9 in the bucket array. If the count in the bucket is non-zero, append that digit index to the string builder as many times as its count specifies.
  6. Print the finished string.

Java Implementation

package io.practise.string;
 
public class PrintMinimumPossibleNumber {
    public static void main(String[] args) {
        String num = "5012267075766";
 
        // 10 digits (0 to 9)
        int[] arr = new int[10];
        char[] chars = num.toCharArray();
 
        // Count frequencies of each digit
        for (char ch : chars) {
            arr[Integer.parseInt(String.valueOf(ch))]++;
        }
 
        StringBuilder stringBuilder = new StringBuilder();
 
        // Append digits in ascending order to construct the minimum number
        for (int i = 0; i < arr.length; ++i) {
            if (arr[i] != 0) {
                for (int j = 1; j <= arr[i]; ++j) {
                    stringBuilder.append(i);
                }
            }
        }
 
        System.out.println("Minimum possible number: " + stringBuilder);
    }
}

Conclusion

By counting frequencies instead of comparisons, we achieve O(N) linear runtime. This makes sorting millions of digits run instantaneously.