Largest Number

Intuition

The tricky part is deciding the order between values like 3 and 30. Comparing their lengths or numeric values does not directly reveal which arrangement is bigger, but comparing the two possible concatenations does: place a before b exactly when the string a+b is greater than b+a. This pairwise rule is consistent enough to sort the entire list, and once sorted in descending order, joining the pieces gives the maximum number. A final guard covers the case where the biggest piece is "0", meaning every value was zero.

Algorithm walkthrough

1. 1Convert every integer to its string form.
2. 2Sort the strings with a comparator that puts a ahead of b when a+b compares greater than b+a.
3. 3Concatenate the sorted strings in order.
4. 4If the first character is '0', the whole result is zeros, so return the single string "0".
5. 5Otherwise return the concatenation as the answer.

Implementation

from functools import cmp_to_key

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        strs = list(map(str, nums))

        def compare(a, b):
            if a + b > b + a:
                return -1
            if a + b < b + a:
                return 1
            return 0

        strs.sort(key=cmp_to_key(compare))
        result = "".join(strs)
        return "0" if result[0] == "0" else result