Largest Number

How it works

Instead of repeatedly scanning for the best number, we can use sorting with a custom comparator. The comparator determines the order by checking if a + b > b + a. By sorting the entire array once using this rule, numbers naturally arrange themselves so that their concatenation yields the largest possible value.

This approach is more efficient because sorting is faster than repeatedly finding and removing the maximum element.

Steps

1. Convert all integers to strings.
2. Sort the strings using a custom comparator: for strings a and b, place a before b if a + b > b + a.
3. Concatenate all sorted strings.
4. Handle the edge case where the result starts with "0" (all zeros) by returning "0".

Complexity

• Time complexity: O(N log N)
• Space complexity: O(N)

Where N is the total number of digits in the array nums.

Things to watch for

Using Numeric Comparison Instead of Concatenation Comparison

Simply sorting numbers by their numeric value does not produce the correct order. For example, 9 should come before 34 because "934" > "349", but 34 > 9 numerically. The correct approach is to compare a + b versus b + a as strings, where + denotes concatenation.

Forgetting the All-Zeros Edge Case

When the input contains only zeros (e.g., [0, 0, 0]), the concatenated result would be "000". The expected output is "0", not "000". Always check if the result starts with '0' and return "0" in that case, since a valid number representation should not have leading zeros unless the number itself is zero.

Incorrect Comparator Logic for Sorting

When implementing a custom comparator, the logic must be consistent. For descending order (largest first), return true when a + b > b + a. Reversing this condition or using the wrong comparison operator will sort elements in ascending order, producing the smallest number instead of the largest.

from typing import List
from functools import cmp_to_key

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        for i, num in enumerate(nums):
            nums[i] = str(num)

        def compare(n1, n2):
            if n1 + n2 > n2 + n1:
                return -1
            else:
                return 1
        nums = sorted(nums, key=cmp_to_key(compare))
        return str(int("".join(nums)))

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        vector<string> arr;
        for (int num : nums) {
            arr.push_back(to_string(num));
        }

        sort(arr.begin(), arr.end(), [](string& a, string& b) {
            return a + b > b + a;
        });

        string res;
        for (string& num : arr) {
            res += num;
        }

        return res[0] == '0' ? "0" : res;
    }
};