Maximum Swap
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.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
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.
| Approach | Time | Space |
|---|---|---|
| Brute force (try every swap) | O(d³) | O(d) |
| Last occurrence of each digit | O(d) | O(d) |
| Optimal (right-to-left running maximum) | O(d) | O(d) |
1Brute force (try every swap)
O(d³)d(d - 1) / 2 swaps, each followed by an O(d) conversion; d <= 9 here.O(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).
- Turn num into a digit array of length d.
- best = num.
- For every pair i < j: swap, evaluate, update best, swap back.
- 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;
}
}class Solution:
def maximumSwap(self, num: int) -> int:
d = list(str(num))
best = num
for i in range(len(d)):
for j in range(i + 1, len(d)):
d[i], d[j] = d[j], d[i]
best = max(best, int(''.join(d)))
d[i], d[j] = d[j], d[i]
return bestclass Solution {
public:
int maximumSwap(int num) {
string d = to_string(num);
int best = num;
for (size_t i = 0; i < d.size(); i++) {
for (size_t j = i + 1; j < d.size(); j++) {
swap(d[i], d[j]);
best = max(best, stoi(d));
swap(d[i], d[j]);
}
}
return best;
}
};function maximumSwap(num) {
const d = String(num).split('');
let best = num;
for (let i = 0; i < d.length; i++) {
for (let j = i + 1; j < d.length; j++) {
[d[i], d[j]] = [d[j], d[i]];
best = Math.max(best, Number(d.join('')));
[d[i], d[j]] = [d[j], d[i]];
}
}
return best;
}2Last occurrence of each digit
O(d)At most 10 candidate digits per position.O(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.
- last[x] = the rightmost index of digit x.
- For i from left to right, for x from 9 down to d[i] + 1:
- If last[x] > i, swap d[i] and d[last[x]] and return the number.
- 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;
}
}class Solution:
def maximumSwap(self, num: int) -> int:
d = list(str(num))
last = {int(c): i for i, c in enumerate(d)}
for i, c in enumerate(d):
for x in range(9, int(c), -1):
if last.get(x, -1) > i:
j = last[x]
d[i], d[j] = d[j], d[i]
return int(''.join(d))
return numclass Solution {
public:
int maximumSwap(int num) {
string d = to_string(num);
int last[10];
fill(last, last + 10, -1);
for (int i = 0; i < (int)d.size(); i++) last[d[i] - '0'] = i;
for (int i = 0; i < (int)d.size(); i++) {
for (int x = 9; x > d[i] - '0'; x--) {
if (last[x] > i) {
swap(d[i], d[last[x]]);
return stoi(d);
}
}
}
return num;
}
};function maximumSwap(num) {
const d = String(num).split('');
const last = new Array(10).fill(-1);
for (let i = 0; i < d.length; i++) last[Number(d[i])] = i;
for (let i = 0; i < d.length; i++) {
for (let x = 9; x > Number(d[i]); x--) {
if (last[x] > i) {
const j = last[x];
[d[i], d[j]] = [d[j], d[i]];
return Number(d.join(''));
}
}
}
return num;
}3Optimal (right-to-left running maximum)
O(d)One pass over the digits.O(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.
- maxIdx = d - 1, swapI = swapJ = -1.
- 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.
- If swapI != -1, swap those two digits.
- 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));
}
}class Solution:
def maximumSwap(self, num: int) -> int:
d = list(str(num))
max_idx, swap_i, swap_j = len(d) - 1, -1, -1
for i in range(len(d) - 2, -1, -1):
if d[i] > d[max_idx]:
max_idx = i
elif d[i] < d[max_idx]:
swap_i, swap_j = i, max_idx
if swap_i == -1:
return num
d[swap_i], d[swap_j] = d[swap_j], d[swap_i]
return int(''.join(d))class Solution {
public:
int maximumSwap(int num) {
string d = to_string(num);
int maxIdx = (int)d.size() - 1, swapI = -1, swapJ = -1;
for (int i = (int)d.size() - 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;
swap(d[swapI], d[swapJ]);
return stoi(d);
}
};function maximumSwap(num) {
const d = String(num).split('');
let maxIdx = d.length - 1, swapI = -1, swapJ = -1;
for (let 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;
[d[swapI], d[swapJ]] = [d[swapJ], d[swapI]];
return Number(d.join(''));
}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.