LeetCode 179: Largest Number

Problem Restatement

We are given a list of non-negative integers nums.

We need to arrange the numbers so that, when they are joined together, they form the largest possible number.

The answer may be very large, so we return it as a string instead of an integer. The official problem states this same requirement: arrange non-negative integers to form the largest number and return it as a string.

Input and Output

Example function shape:

def largestNumber(nums: list[int]) -> str:
    ...

Examples

Example 1:

nums = [10, 2]

There are two possible orders:

10 + 2 = "102"
2 + 10 = "210"

The larger result is:

"210"

So the answer is:

"210"

Example 2:

nums = [3, 30, 34, 5, 9]

The best order is:

9, 5, 34, 3, 30

Joining them gives:

"9534330"

So the answer is:

"9534330"

First Thought: Sort Numbers Descending

A first attempt is to sort the numbers from largest to smallest.

For example:

nums = [10, 2]

Numeric descending order gives:

[10, 2]

That produces:

"102"

But the better answer is:

"210"

So normal numeric sorting fails.

The issue is that we are not comparing numbers by their standalone values. We are comparing them by how they behave when placed next to another number.

Key Insight

For two numbers a and b, there are only two possible orders:

a before b: ab
b before a: ba

We should place a before b if:

ab > ba

For example, compare 3 and 30.

"3" + "30" = "330"
"30" + "3" = "303"

Since:

"330" > "303"

3 should come before 30.

Compare 9 and 34.

"9" + "34" = "934"
"34" + "9" = "349"

Since:

"934" > "349"

9 should come before 34.

This gives us a custom sorting rule.

Algorithm

1. Convert every number into a string.
2. Sort the strings with a custom comparison:
   • Put a before b if a + b > b + a.
   • Put b before a otherwise.
3. Join the sorted strings.
4. If the first character is "0", return "0".

The last step handles inputs like:

[0, 0]

Without the special case, joining gives:

"00"

But the correct answer is:

"0"

Correctness

Consider any two adjacent numbers in the final arrangement, written as strings a and b.

If a + b is greater than b + a, then placing a before b gives a larger result than placing b before a.

So the better local order is:

a, b

If b + a is greater than a + b, then the better local order is:

b, a

The custom sort applies this rule across all pairs that matter for ordering. After sorting, no adjacent pair can be swapped to make the final string larger.

Therefore, the joined result is the largest possible concatenation.

If the largest sorted string is "0", then every number must be 0, because all numbers are non-negative. In that case, the only valid largest number is "0".

Complexity

Here, n is the number of integers, and k is the maximum number of digits in one integer.

Implementation

from functools import cmp_to_key

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

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

        parts.sort(key=cmp_to_key(compare))

        if parts[0] == "0":
            return "0"

        return "".join(parts)

Code Explanation

We first convert all numbers to strings:

parts = [str(num) for num in nums]

This makes concatenation easy.

The comparator decides the order of two strings:

if a + b > b + a:
    return -1

Returning -1 means a should come before b.

This line sorts using the custom comparator:

parts.sort(key=cmp_to_key(compare))

Python sorting normally uses keys, not comparators. cmp_to_key adapts the comparator into a key object Python can sort.

After sorting, we handle the all-zero case:

if parts[0] == "0":
    return "0"

If the largest element after sorting is "0", then all elements are zero.

Finally, we join the strings:

return "".join(parts)

Testing

def run_tests():
    s = Solution()

    assert s.largestNumber([10, 2]) == "210"
    assert s.largestNumber([3, 30, 34, 5, 9]) == "9534330"
    assert s.largestNumber([0, 0]) == "0"
    assert s.largestNumber([1]) == "1"
    assert s.largestNumber([121, 12]) == "12121"
    assert s.largestNumber([8308, 8308, 830]) == "83088308830"

    print("all tests passed")

run_tests()

Test meaning: