LeetCode 670 - Maximum Swap

The problem asks us to take an integer num and find the maximum number we can create by swapping at most two digits. In other words, we can pick two positions in the number, swap their digits, and we want the resulting number to be as large as possible.

leetcodemediummathgreedy

LeetCode Problem 670

Difficulty: 🟡 Medium
Topics: Math, Greedy

Solution

Problem Understanding

The problem asks us to take an integer num and find the maximum number we can create by swapping at most two digits. In other words, we can pick two positions in the number, swap their digits, and we want the resulting number to be as large as possible. If no swap would increase the number, we simply return the original number.

The input num is guaranteed to be a non-negative integer up to 10^8. This means the number can have at most 9 digits. The expected output is a single integer, representing the largest number obtainable from num by at most one swap.

Important edge cases include numbers that are already in descending order, numbers with repeated digits, and numbers with leading zeros after a potential swap (though the swap cannot introduce an actual leading zero since num >= 0).

Approaches

Brute Force Approach

A brute-force approach would consider every possible pair of digit positions, swap them, and track the maximum number obtained. For a number with n digits, this requires checking all pairs (i, j) with 0 <= i < j < n. After each swap, the integer value must be computed to see if it is larger than the current maximum. This approach is correct because it exhaustively checks every possibility, but it is inefficient: for 9 digits, we would perform 36 swaps, and for larger numbers this could grow significantly. Time complexity would be O(n^2) for swaps multiplied by O(n) to reconstruct the number from digits, making it O(n^3) in total.

Optimal Approach

The key observation for an optimal solution is that the largest possible number is obtained by swapping the first smaller digit (from left) with the largest digit that appears after it. To implement this:

  1. Convert the number into a list of digits.
  2. Track the last occurrence of each digit (0-9).
  3. Traverse the digits from left to right, and for each digit, check if there is a larger digit later in the number (starting from 9 down to current digit + 1).
  4. Swap the first such pair and return the result.

This approach works in linear time O(n) and uses O(1) extra space (constant 10-element array for last positions). The reasoning is that by swapping the leftmost smaller digit with the largest possible digit to its right, we maximize the value as early as possible in the number.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^3) O(n) Check all possible swaps, reconstruct integer each time
Optimal O(n) O(1) Use last occurrence mapping and greedy left-to-right swap

Algorithm Walkthrough

  1. Convert the integer num to a list of digits so we can access and swap them easily.
  2. Create a last array or dictionary to store the last occurrence index of each digit (0-9). This helps us quickly identify where the largest digit appears later in the number.
  3. Iterate through the list of digits from left to right. For each digit d at index i, check digits from 9 down to d + 1.
  4. If a larger digit d_larger exists and its last occurrence j is after i, swap digits[i] and digits[j]. This guarantees we increase the number maximally by making the first significant leftward swap.
  5. Convert the digits list back to an integer and return it. If no swap is found, return the original number.

Why it works: The algorithm ensures the leftmost digit that can be increased is swapped with the largest available digit to its right. Any later swap would not have as large an impact because digits to the left are more significant in determining the number’s value. This guarantees a global maximum with at most one swap.

Python Solution

class Solution:
    def maximumSwap(self, num: int) -> int:
        digits = list(str(num))
        last = {int(d): i for i, d in enumerate(digits)}
        
        for i, d in enumerate(digits):
            for larger in range(9, int(d), -1):
                if last.get(larger, -1) > i:
                    digits[i], digits[last[larger]] = digits[last[larger]], digits[i]
                    return int("".join(digits))
        return num

The Python solution first converts the number to a list of its digits, then creates a mapping of each digit to its last position. It checks for possible swaps with larger digits in descending order, ensuring the first swap maximizes the value. If no such swap exists, it returns the original number.

Go Solution

func maximumSwap(num int) int {
    digits := []byte(fmt.Sprintf("%d", num))
    last := [10]int{}
    for i, d := range digits {
        last[d-'0'] = i
    }

    for i := 0; i < len(digits); i++ {
        for d := 9; d > int(digits[i]-'0'); d-- {
            if last[d] > i {
                digits[i], digits[last[d]] = digits[last[d]], digits[i]
                res, _ := strconv.Atoi(string(digits))
                return res
            }
        }
    }
    return num
}

The Go implementation follows the same logic as Python. A byte slice represents the digits, and an array tracks the last occurrence of each digit. strconv.Atoi converts the slice back to an integer. No special handling is required for edge cases since num is guaranteed non-negative.

Worked Examples

Example 1: num = 2736

Index Digit Last occurrence Swap Check
0 2 1:7, 2:7, 3:3, 6:3 9→3 no, 8→3 no, 7→1 yes → swap 2 and 7
Result 7236

Example 2: num = 9973

Index Digit Last occurrence Swap Check
0 9 0 9→ no
1 9 1 9→ no
2 7 2 8,9→ no
3 3 3 4→9 no
Result 9973 No swap possible

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each digit is checked once, inner loop runs at most 9 iterations
Space O(1) Constant array or dict of size 10 for last occurrence tracking

The algorithm scales linearly with the number of digits in num. Space is minimal and independent of input size due to the fixed range of digits (0-9).

Test Cases

# Provided examples
assert Solution().maximumSwap(2736) == 7236  # simple swap
assert Solution().maximumSwap(9973) == 9973  # no swap needed

# Edge cases
assert Solution().maximumSwap(0) == 0        # single-digit number
assert Solution().maximumSwap(10) == 10      # swap would not increase value
assert Solution().maximumSwap(1993) == 9913  # swap first 1 with last 9
assert Solution().maximumSwap(98368) == 98863 # swap first 3 with last 8
assert Solution().maximumSwap(12345) == 52341 # swap 1 with 5
assert Solution().maximumSwap(54321) == 54321 # already max
Test Why
2736 Tests basic swap
9973 No swap scenario
0 Single-digit edge case
10 Swap does not improve
1993 Swap increases number by moving smaller left digit
98368 Swap in middle digits
12345 Swap first and last digits for max
54321 Already maximum number

Edge Cases

One important edge case is a single-digit number, such as 0 or 7. Since there is no other digit to swap with, the function must return the number itself. The implementation handles this because the loops never find a larger digit to swap with.

Another edge case is numbers with repeated digits, like 9973. Multiple occurrences of the same digit can confuse naive algorithms that pick the first occurrence rather than the last. By tracking the last occurrence of each digit, the solution guarantees that the largest swap is chosen.

Finally, numbers that are already in descending order, such as 54321, must return the original number. Any swap would decrease the value, so the function should correctly detect that no beneficial swap exists and return the original integer. The algorithm naturally handles this by only swapping when a larger digit is found later.