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

Example function shape:

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

Examples

Consider:

num = 2736

We can swap 2 and 7:

2736 -> 7236

The maximum result is:

7236

Another example:

num = 9973

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

So we do not need to swap anything.

The answer is:

9973

Another example:

num = 98368

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

98368 -> 98863

The answer is:

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:

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:

num = 2736

At the first digit:

2

there is a larger digit on the right:

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:

num = 98368

The digit 3 can be swapped with 8.

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

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

Here, d is the number of digits in num.

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

Implementation

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:

digits = list(str(num))

Then we record the last position of each digit:

last = {}

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

For example, in:

98368

the last index of digit 8 is the final position.

Then we scan from left to right:

for i, digit in enumerate(digits):

At each position, we look for a better digit:

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

This checks the largest possible replacement first.

If a larger digit exists to the right:

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

we swap:

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

Then we return immediately:

return int("".join(digits))

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

return num

Testing

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: