Form the Largest Number

Problem Summary

Given an array of non-negative integers, arrange them so that after concatenation they form the largest possible number.

Return the result as a string (because it can be very large).

Key Insight

This is NOT normal sorting.

We compare numbers based on:

(a + b) vs (b + a)

Whichever concatenation is larger should come first.

Why This Works

Suppose:

• a = "3"

• b = "30"

Compare:

• "330" vs "303"

"330" is larger → so "3" comes before "30".

Strategy

• Convert numbers to strings

• Sort using custom comparator:

(b + a).compareTo(a + b)

• Concatenate result

• Handle edge case: all zeros

Edge Case

If array is like:

[0, 0, 0]

Return "0" (not "000")

Java Solution

import java.util.*;

class Solution {
    public String findLargest(int[] arr) {

        String[] s = new String[arr.length];

        for (int i = 0; i < arr.length; i++) {
            s[i] = String.valueOf(arr[i]);
        }

        Arrays.sort(s, (a, b) -> (b + a).compareTo(a + b));

        // Edge case: all zeros
        if (s[0].equals("0")) {
            return "0";
        }

        StringBuilder sb = new StringBuilder();

        for (String str : s) {
            sb.append(str);
        }

        return sb.toString();
    }
}

Example Walkthrough

Input:

[3, 30, 34, 5, 9]

After sorting:

[9, 5, 34, 3, 30]

Output:

9534330

Complexity

• Time Complexity: O(n log n) (sorting)

• Space Complexity: O(n) (string array)

Key Takeaways

• This is a greedy sorting problem

• Normal sorting does NOT work

• Custom rule: compare (a + b) vs (b + a)

• Very common interview question (Amazon, Microsoft, Paytm)

Pattern Recognition

If you see:

• “arrange to form largest/smallest number”

• “concatenate strings/numbers”

• “ordering matters”

Think:

Custom Comparator Sorting (Greedy)

Summary

This problem demonstrates how greedy strategy combined with custom comparator sorting can solve non-trivial ordering problems. By comparing concatenated pairs instead of individual values, we ensure the globally optimal arrangement that yields the largest possible number.