# 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

| Item | Meaning |
|---|---|
| Input | A list of non-negative integers `nums` |
| Output | A string representing the largest possible concatenated number |
| Constraint | We may reorder the numbers |
| Important detail | The result should be returned as a string |

Example function shape:

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

## Examples

Example 1:

```python
nums = [10, 2]
```

There are two possible orders:

```text
10 + 2 = "102"
2 + 10 = "210"
```

The larger result is:

```text
"210"
```

So the answer is:

```python
"210"
```

Example 2:

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

The best order is:

```text
9, 5, 34, 3, 30
```

Joining them gives:

```text
"9534330"
```

So the answer is:

```python
"9534330"
```

## First Thought: Sort Numbers Descending

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

For example:

```python
nums = [10, 2]
```

Numeric descending order gives:

```python
[10, 2]
```

That produces:

```text
"102"
```

But the better answer is:

```text
"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:

```text
a before b: ab
b before a: ba
```

We should place `a` before `b` if:

```text
ab > ba
```

For example, compare `3` and `30`.

```text
"3" + "30" = "330"
"30" + "3" = "303"
```

Since:

```text
"330" > "303"
```

`3` should come before `30`.

Compare `9` and `34`.

```text
"9" + "34" = "934"
"34" + "9" = "349"
```

Since:

```text
"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:

```python
[0, 0]
```

Without the special case, joining gives:

```text
"00"
```

But the correct answer is:

```text
"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:

```text
a, b
```

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

```text
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n log n * k)` | Sorting takes `O(n log n)` comparisons, and each comparison concatenates strings of length up to `k` |
| Space | `O(nk)` | We store the string form of each number and the final result |

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

## Implementation

```python
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:

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

This makes concatenation easy.

The comparator decides the order of two strings:

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

Returning `-1` means `a` should come before `b`.

This line sorts using the custom comparator:

```python
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:

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

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

Finally, we join the strings:

```python
return "".join(parts)
```

## Testing

```python
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:

| Test | Why |
|---|---|
| `[10, 2]` | Shows why numeric descending sort fails |
| `[3, 30, 34, 5, 9]` | Main mixed-length example |
| `[0, 0]` | Checks all-zero output |
| `[1]` | Minimum simple case |
| `[121, 12]` | Checks prefix-like numbers |
| `[8308, 8308, 830]` | Checks repeated and prefix-related values |