# LeetCode 670: Maximum Swap

## Problem Restatement

We are given a non-negative integer `num`.

We may swap two digits at most once.

Return the maximum possible value we can get after doing zero or one swap. The official statement asks us to swap two digits at most once to get the maximum valued number.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A non-negative integer `num` |
| Output | The maximum integer possible after at most one digit swap |
| Allowed operation | Swap two digits once |
| Swap count | Zero or one swap |

Example function shape:

```python
def maximumSwap(num: int) -> int:
    ...
```

## Examples

Consider:

```python
num = 2736
```

We can swap `2` and `7`:

```text
2736 -> 7236
```

The maximum result is:

```python
7236
```

Another example:

```python
num = 9973
```

The digits are already arranged to produce the largest possible number.

So we do not need to swap anything.

The answer is:

```python
9973
```

Another example:

```python
num = 98368
```

The best swap is to swap `3` with the last `8`:

```text
98368 -> 98863
```

The answer is:

```python
98863
```

## First Thought: Try Every Swap

A direct solution is to try every pair of digit positions.

For each pair:

1. Swap the digits.
2. Convert the result back to an integer.
3. Track the maximum value.

This works, but if the number has `d` digits, there are about:

```text
d * d
```

possible swaps.

The constraints are small enough that this could pass, but we can solve it more directly with a greedy idea.

## Key Insight

To maximize a number, the most important digit is the leftmost digit.

So we want to find the earliest position where we can replace the current digit with a larger digit from the right.

For example:

```python
num = 2736
```

At the first digit:

```text
2
```

there is a larger digit on the right:

```text
7
```

Swapping them gives the largest improvement because it changes the highest-place digit possible.

If there are multiple copies of the larger digit, we should use the rightmost one.

For example:

```python
num = 98368
```

The digit `3` can be swapped with `8`.

There are two `8`s in the number, but the rightmost `8` is better:

```text
98368 -> 98863
```

Using the earlier `8` would give no useful improvement.

## Greedy Strategy

Store the last index where each digit appears.

Then scan the number from left to right.

For each current digit `d`, try to find a larger digit from `9` down to `d + 1`.

If a larger digit exists to the right, swap with its last occurrence and return immediately.

Returning immediately is correct because improving an earlier digit gives a larger number than any improvement made later.

## Algorithm

1. Convert `num` into a list of digit characters.
2. Store the last index of every digit.
3. Scan each digit from left to right.
4. For the current digit, check larger digits from `9` down to `current + 1`.
5. If a larger digit appears later:
   - Swap the current digit with that larger digit.
   - Return the resulting integer.
6. If no beneficial swap exists, return `num`.

## Correctness

The algorithm scans digits from the most significant position to the least significant position.

The first position where a larger digit exists to the right is the best place to perform a swap, because increasing an earlier digit dominates any possible change at later positions.

For that position, the algorithm tries larger digits from `9` down to the current digit plus one. Therefore, it chooses the largest possible digit that can be moved into this position.

If that largest digit appears multiple times to the right, the algorithm uses its last occurrence. This keeps the larger digit at the current position while moving the smaller current digit as far right as possible, which maximizes the remaining suffix.

After performing this swap, no later swap can improve the number more, and only one swap is allowed. Therefore, returning immediately gives the maximum possible value.

If the scan finishes without finding a larger digit to the right of any position, the digits are already in non-increasing order. No swap can improve the number, so returning the original value is correct.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(d)` | We scan the digits and check at most 10 possible larger digits each time |
| Space | `O(d)` | We store the digit list |

Here, `d` is the number of digits in `num`.

Since decimal digits are only `0` through `9`, the inner loop is constant size.

## Implementation

```python
class Solution:
    def maximumSwap(self, num: int) -> int:
        digits = list(str(num))

        last = {}

        for i, digit in enumerate(digits):
            last[int(digit)] = i

        for i, digit in enumerate(digits):
            current = int(digit)

            for larger in range(9, current, -1):
                if larger in last and last[larger] > i:
                    j = last[larger]
                    digits[i], digits[j] = digits[j], digits[i]
                    return int("".join(digits))

        return num
```

## Code Explanation

We convert the number into a mutable list:

```python
digits = list(str(num))
```

Then we record the last position of each digit:

```python
last = {}

for i, digit in enumerate(digits):
    last[int(digit)] = i
```

For example, in:

```python
98368
```

the last index of digit `8` is the final position.

Then we scan from left to right:

```python
for i, digit in enumerate(digits):
```

At each position, we look for a better digit:

```python
for larger in range(9, current, -1):
```

This checks the largest possible replacement first.

If a larger digit exists to the right:

```python
if larger in last and last[larger] > i:
```

we swap:

```python
j = last[larger]
digits[i], digits[j] = digits[j], digits[i]
```

Then we return immediately:

```python
return int("".join(digits))
```

If no swap improves the number, return the original value:

```python
return num
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.maximumSwap(2736) == 7236
    assert s.maximumSwap(9973) == 9973
    assert s.maximumSwap(98368) == 98863
    assert s.maximumSwap(1993) == 9913
    assert s.maximumSwap(0) == 0
    assert s.maximumSwap(9) == 9
    assert s.maximumSwap(10909091) == 90909011

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `2736` | Standard example with an early beneficial swap |
| `9973` | Already maximum |
| `98368` | Requires using the rightmost best digit |
| `1993` | Multiple copies of the largest digit |
| `0` | Smallest input |
| `9` | Single digit cannot improve |
| `10909091` | Checks last occurrence logic with repeated digits |