Maximum Swap

Share

Swap two digits at most once in a number to maximize it. Return the max result.

Example 1
Input: num=2736 → Output: 7236. Swap 7 and 2.
Example 2
Input: num=9973 → Output: 9973

Solution Approach

Record last occurrence of each digit 0-9. For each digit from left, check if a larger digit appears later.

  • Convert to char array
  • Record last index of each digit 0-9
  • For each position from left
  • Check digits 9 down to current+1
  • If larger digit exists later, swap and return
  • Return original number
Java
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 tmp = digits[i];
                digits[i] = digits[last[d]];
                digits[last[d]] = tmp;
                return Integer.parseInt(new String(digits));
            }
        }
    }
    return num;
}
  • Time Complexity: O(n)
  • Space Complexity: O(1)