Constructing the Minimum Possible Number using Counting Sort

What We're Solving & Complexity Bounds

Arranging a collection of numeric digits to construct the smallest representation is a common algorithmic puzzle. If you are given a long string of numeric digits, such as "50122", and asked to rearrange the digits to construct the smallest possible number, the standard approach is to perform comparison-based character sorting. However, standard sorting algorithms like Merge Sort or Quick Sort require O(n log n) time.

Since the range of digits is extremely small and fixed (only ten possible digits: 0 through 9), we can optimize this sorting task to a linear O(n) runtime using Counting Sort (also known as bucket sort logic). By allocating a small bucket array to count frequencies, we eliminate character comparisons entirely.

The Strategy

Algorithmic Mechanics (Bucket Allocation)

Let's look at the implementation details of this linear-time sorting method:

• Frequency Array: We allocate an integer array arr of size 10 (indices 0 to 9) to store digit counts.
• Single-Pass Accumulation: We convert the input string to a character array and loop through it once. For each character, we determine its numeric value and increment the corresponding index in our frequency array: arr[digit]++.
• String Assembly: We initialize a StringBuilder. We loop through our frequency array from index 0 to 9. If the count at the current index i is non-zero, we append the digit i to our string builder exactly as many times as its count specifies.
• Printing the Result: The final constructed string represents the minimum possible number.

Detailed Trace Walkthrough

Let's trace this counting sort execution step-by-step using the input string "5012267075766":

1. Step 1 (Initialize Buckets):
   • Create frequency array arr of size 10, initialized to all zeros.
2. Step 2 (Frequencies Scan):
   • Traverse the input characters: 5, 0, 1, 2, 2, 6, 7, 0, 7, 5, 7, 6, 6.
   • Update frequency indices:
     • arr[0] = 2 (digits: 0, 0)
     • arr[1] = 1 (digits: 1)
     • arr[2] = 2 (digits: 2, 2)
     • arr[5] = 2 (digits: 5, 5)
     • arr[6] = 3 (digits: 6, 6, 6)
     • arr[7] = 3 (digits: 7, 7, 7)
3. Step 3 (Reconstruction):
   • We scan from index 0 to 9:
     • Index 0 count is 2 → Append "00".
     • Index 1 count is 1 → Append "1".
     • Index 2 count is 2 → Append "22".
     • Index 5 count is 2 → Append "55".
     • Index 6 count is 3 → Append "666".
     • Index 7 count is 3 → Append "777".
4. Step 4 (Completion):
   • The resulting string builder content is "0012255666777", which is printed to the console.

Code Highlights & Explanations

Key aspects of our Java implementation:

• Integer.parseInt(String.valueOf(ch)) parses each character digit into its corresponding bucket index.
• The nested loops reconstruction prints digits in sorted order without utilizing any comparator logic.

The Java Code

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 & Takeaways

By replacing comparison-based sorting with element frequency counting, we achieve O(N) linear runtime. This makes sorting millions of digits run instantaneously. This optimization is a powerful reminder that bounded data ranges allow us to bypass general-case complexity bounds entirely.