Maximum Swap

Medium Arrays & Hashing Right to Left Traversal Original on LeetCode

Reported atMetaCRED

Maximum Swap is a medium arrays & hashing problem solved with the right to left traversal pattern. The best approach, optimal (right-to-left running maximum), runs in O(d) time and O(d) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (try every swap) up.

Problem

You are given a non-negative integer num. You may swap two digits of it at most once (or not swap at all).

Return the largest number you can get this way.

Examples

Example 1

Input
num = 4719
Output
9714
Why
Swapping the leading 4 with the 9 at the end gives the largest possible number.

Example 2

Input
num = 8531
Output
8531
Why
The digits already decrease from left to right, so any swap would make the number smaller; keep it.

Example 3

Input
num = 1993
Output
9913
Why
Swap the 1 with the LAST 9, not the first one: 9913 beats 9193.

Constraints

  • 0 <= num <= 10^8
  • At most one swap of two digits is allowed (zero swaps is fine).

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (try every swap)O(d³)O(d)
Last occurrence of each digitO(d)O(d)
Optimal (right-to-left running maximum)O(d)O(d)

1Brute force (try every swap)

TimeO(d³)d(d - 1) / 2 swaps, each followed by an O(d) conversion; d <= 9 here.
SpaceO(d)The digit array.

The number has at most 9 digits, so try swapping every pair of positions, turn the digits back into a number and keep the largest result (starting from the number itself, which covers the no-swap case).

  1. Turn num into a digit array of length d.
  2. best = num.
  3. For every pair i < j: swap, evaluate, update best, swap back.
  4. Return best.
class Solution {
    public int maximumSwap(int num) {
        char[] d = Integer.toString(num).toCharArray();
        int best = num;
        for (int i = 0; i < d.length; i++) {
            for (int j = i + 1; j < d.length; j++) {
                char t = d[i]; d[i] = d[j]; d[j] = t;
                best = Math.max(best, Integer.parseInt(new String(d)));
                t = d[i]; d[i] = d[j]; d[j] = t;
            }
        }
        return best;
    }
}

2Last occurrence of each digit

TimeO(d)At most 10 candidate digits per position.
SpaceO(d)The digit array plus a 10-slot table.

Record the last index of every digit 0..9. Then scan from the left: for position i, look for a digit bigger than d[i], trying 9 first and going down, whose last index is to the right of i. The first such hit is the best possible swap, because it upgrades the leftmost position with the biggest digit, taken from its rightmost copy.

  1. last[x] = the rightmost index of digit x.
  2. For i from left to right, for x from 9 down to d[i] + 1:
  3. If last[x] > i, swap d[i] and d[last[x]] and return the number.
  4. If the loop finishes, return num unchanged.
class Solution {
    public int maximumSwap(int num) {
        char[] d = Integer.toString(num).toCharArray();
        int[] last = new int[10];
        for (int i = 0; i < d.length; i++) last[d[i] - '0'] = i;
        for (int i = 0; i < d.length; i++) {
            for (int x = 9; x > d[i] - '0'; x--) {
                if (last[x] > i) {
                    char t = d[i]; d[i] = d[last[x]]; d[last[x]] = t;
                    return Integer.parseInt(new String(d));
                }
            }
        }
        return num;
    }
}

3Optimal (right-to-left running maximum)

TimeO(d)One pass over the digits.
SpaceO(d)The digit array (d <= 9, so effectively constant).

Scan from the right, keeping the index of the largest digit seen so far (update it only on a strictly larger digit, so ties keep the rightmost copy). Whenever the current digit is smaller than that maximum, (i, maxIdx) is a swap that helps; since the scan moves left, the last such pair recorded is the one with the leftmost i, which is the best swap.

  1. maxIdx = d - 1, swapI = swapJ = -1.
  2. For i from d - 2 down to 0: if digit[i] > digit[maxIdx], maxIdx = i; else if digit[i] < digit[maxIdx], set swapI = i, swapJ = maxIdx.
  3. If swapI != -1, swap those two digits.
  4. Return the resulting number.
class Solution {
    public int maximumSwap(int num) {
        char[] d = Integer.toString(num).toCharArray();
        int maxIdx = d.length - 1, swapI = -1, swapJ = -1;
        for (int i = d.length - 2; i >= 0; i--) {
            if (d[i] > d[maxIdx]) {
                maxIdx = i;
            } else if (d[i] < d[maxIdx]) {
                swapI = i;
                swapJ = maxIdx;
            }
        }
        if (swapI == -1) return num;
        char t = d[swapI]; d[swapI] = d[swapJ]; d[swapJ] = t;
        return Integer.parseInt(new String(d));
    }
}

Edge cases to test

  • Single-digit numbers, including 0
  • Digits already in non-increasing order: return num unchanged
  • The largest digit appears several times: swap with its rightmost copy
  • All digits equal
  • Zeros inside the number, like 10 or 100

Hints

Hint 1

To make the number as large as possible, improve the leftmost position you can.

Hint 2

A position i can be improved if some digit to its right is bigger. Which bigger digit should it take, and from which copy?

Hint 3

Scanning from the right while remembering the position of the largest digit so far tells you, for every i, the best digit available to its right.

FAQ

What is the best time complexity for Maximum Swap?

Optimal (right-to-left running maximum) runs in O(d) time and O(d) extra space. One pass over the digits.

Which pattern does Maximum Swap use?

It is a arrays & hashing problem that uses the right to left traversal pattern. Other problems with the same pattern: Array Leaders, Product of Array Except Self, Next Permutation.

Is there a brute force solution for Maximum Swap?

Yes. Brute force (try every swap) takes O(d³) time and O(d) space. The number has at most 9 digits, so try swapping every pair of positions, turn the digits back into a number and keep the largest result (starting from the number itself, which covers the no-swap case).

Which edge cases should I test for Maximum Swap?

Single-digit numbers, including 0; Digits already in non-increasing order: return num unchanged; The largest digit appears several times: swap with its rightmost copy; All digits equal; Zeros inside the number, like 10 or 100.