179. Largest Number

Intuition

To determine which of two numbers a and b should come first, compare the concatenations "ab" and "ba" as strings. If "ab" > "ba", place a before b. Sort all numbers using this comparator, then join.

Algorithm

1Convert all integers to strings.
2Sort with custom comparator: compare(a, b) = (b+a).CompareTo(a+b) - descending order (larger concat first).
3If the first element of sorted array is "0", return "0" (all zeros case).
4Join sorted strings and return.

Example Walkthrough

Input: [3,30,34,5,9]

1.Compare 3 vs 30: "330" vs "303" -> 330>303, 3 first.
2.Compare 34 vs 3: "343" vs "334" -> 343>334, 34 first.
3.Sorted: [9,5,34,3,30]. Joined: "9534330".

Output: "9534330"

Common Pitfalls

•The all-zeros edge case: sorted order would give "0000..." - return "0" instead.

179.cs

// Approach: The key insight is that to decide whether string a should precede string b,
// compare the concatenations a+b and b+a lexicographically — prefer whichever is larger.
// This custom comparator is transitive, so Array.Sort with it produces a correct total ordering.
// After sorting, concatenate all strings to form the largest number.
// Handle the edge case where all values are zero: if the result starts with '0', return "0".
// Time: O(n log n x L) where L is the average number of digits. Space: O(n) for the string array.

public class Solution
{
    public string LargestNumber(int[] nums)
    {
        // Create a list of strings to store the numbers as strings
        List<string> stringNumbers = new List<string>();

        // Convert each integer in the array to a string and add it to the list
        foreach (int num in nums)
            stringNumbers.Add(num.ToString());

        // Sort the list using a custom comparator
        // The custom comparator defines the order based on the concatenation result
        // This ensures that the largest number is formed after sorting
        stringNumbers.Sort((str1, str2) => (str2 + str1).CompareTo(str1 + str2));

        // After sorting, if the largest number is "0", it means all numbers were zeros
        // In that case, return "0"
        if (stringNumbers[0] == "0")
            return "0";

        // Join all the strings in the list to get the final largest number representation
        return string.Join("", stringNumbers);
    }
}

Was this solution helpful?