Problem Description

Given a non-negative integer num, you are allowed to swap two digits at most once to get the maximum valued number possible. Return the maximum number you can get.

• You can swap any two different digits in num (not necessarily adjacent).
• Only one swap is allowed; if no swap can improve the number, return num itself.
• All digits must remain in their original order except for the two you swap.

Constraints:

• 0 <= num <= 10^8
• There is always exactly one valid answer.

Thought Process

To maximize the number by swapping two digits, we want to bring the largest possible digit as far to the left as possible. The naive or brute-force approach would be to try all possible pairs of digits, swap them, and check which swap gives the largest number. However, this is inefficient, especially for numbers with many digits.

Instead, we can optimize by observing that the leftmost digit that can be increased by swapping with a larger digit on its right should be swapped. The key is to find the first position from the left where a larger digit exists somewhere to its right, and swap it with the largest such digit as far to the right as possible.

This approach avoids unnecessary swaps and ensures the maximal number is achieved in a single pass.

Solution Approach

Let's break down the steps for an efficient solution:

1. Convert the number to a list of digits:
   • This makes it easy to swap digits and compare them.
2. Record the last occurrence of each digit (0-9):
   • We use an array or hashmap to store, for each digit, the index of its last appearance in the number.
   • This allows us to quickly find out if a larger digit appears later in the number.
3. Scan the digits from left to right:
   • For each digit, check if there's a larger digit (from 9 down to current digit + 1) that appears later in the number.
   • If such a digit is found, swap the current digit with the last occurrence of that larger digit.
   • Return the new number immediately, as only one swap is allowed.
4. If no swap is made:
   • The number is already the largest possible, so return it as is.

We use a last-occurrence map because it lets us quickly find the best digit to swap with in O(1) time per digit.

Example Walkthrough

Let's walk through the process with num = 2736:

1. Convert 2736 to digits: [2, 7, 3, 6]
2. Record last occurrence for each digit:
   • 2 at index 0
   • 3 at index 2
   • 6 at index 3
   • 7 at index 1
3. Start scanning from left:
   • At index 0 (digit 2): Look for larger digits from 9 down to 3.
     • 7 is larger and occurs at index 1.
     • Swap 2 (index 0) with 7 (index 1): [7, 2, 3, 6]
     • Resulting number: 7236
4. Since a swap was made, return 7236.

If no larger digit exists to the right of any digit, the number is already maximal.

Time and Space Complexity

• Brute-force approach:
  • Try all pairs of digits: O(n^2), where n is the number of digits.
  • Space: O(n) for storing digits.
• Optimized approach (as described above):
  • Converting number to digits: O(n)
  • Recording last occurrence: O(n)
  • Scanning and swapping: O(n)
  • Total time: O(n)
  • Space: O(n) for the digits list and O(1) for the last-occurrence array (since it's always size 10).

The optimized approach is much more efficient and scalable, especially for larger numbers.

Code Implementation

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

class Solution {
public:
    int maximumSwap(int num) {
        string s = to_string(num);
        int last[10] = {0};
        for (int i = 0; i < s.size(); ++i) {
            last[s[i] - '0'] = i;
        }
        for (int i = 0; i < s.size(); ++i) {
            for (int d = 9; d > s[i] - '0'; --d) {
                if (last[d] > i) {
                    swap(s[i], s[last[d]]);
                    return stoi(s);
                }
            }
        }
        return num;
    }
};
      

class Solution {
    public int maximumSwap(int num) {
        char[] digits = Integer.toString(num).toCharArray();
        int[] last = new int[10];
        for (int i = 0; i < digits.length; i++) {
            last[digits[i] - '0'] = i;
        }
        for (int i = 0; i < digits.length; i++) {
            for (int d = 9; d > digits[i] - '0'; d--) {
                if (last[d] > i) {
                    char temp = digits[i];
                    digits[i] = digits[last[d]];
                    digits[last[d]] = temp;
                    return Integer.parseInt(new String(digits));
                }
            }
        }
        return num;
    }
}
      

var maximumSwap = function(num) {
    let digits = num.toString().split('');
    let last = new Array(10).fill(-1);
    for (let i = 0; i < digits.length; i++) {
        last[parseInt(digits[i])] = i;
    }
    for (let i = 0; i < digits.length; i++) {
        for (let d = 9; d > parseInt(digits[i]); d--) {
            if (last[d] > i) {
                let temp = digits[i];
                digits[i] = digits[last[d]];
                digits[last[d]] = temp;
                return parseInt(digits.join(''));
            }
        }
    }
    return num;
};
      

Summary

The Maximum Swap problem asks us to maximize a number by swapping two digits at most once. The key insight is to swap the leftmost digit with the largest possible digit to its right, using a last-occurrence lookup for efficiency. This yields an optimal solution in linear time, making the approach both elegant and practical for large numbers.