Maximum Swap — Solution in Python, Java & C++
Maximum Swap solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon and Google.
Maximum Swap is a medium coding problem on math and greedy, asked in Amazon, Google, Microsoft and Meta interviews.
- Difficulty: Medium
- Topics: Math, Greedy
- Asked at: Amazon, Google, Microsoft, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an integer num. You may swap two of its digits at most once.
Return the maximum value you can obtain.
Example 1
Input: num = 2736
Output: 7236
Explanation: Swap the 2 and the 7.
Example 2
Input: num = 9973
Output: 9973
Explanation: No swap improves it.
Example 3
Input: num = 1993
Output: 9913
Constraints
0 <= num <= 100000000
Hints for Maximum Swap
Hint 1
Scan from the most significant digit; the first place you can raise is where the swap belongs.
Hint 2
For that position, bring in the largest digit that appears later.
Hint 3
If that largest digit occurs several times later, take the rightmost occurrence — moving a digit from further right leaves more value behind.
How to solve Maximum Swap
Scan from the left for the first position that can be raised; swap in the largest digit that appears later, taking its rightmost occurrence.
Approach
- Record the last index of each digit.
- For each position
i, forbiggerfrom 9 down todigit + 1: ifbiggeroccurs afteri, swap with its last occurrence and return.
Why it works
Raising the most significant possible position gives the biggest gain; among candidates for that position the largest digit wins; and taking the rightmost occurrence moves the smaller digit as far right as possible.
Complexity
- Time —
O(digits) - Space —
O(1)
Pitfalls
- Swapping with the first occurrence of the bigger digit can be worse —
1993→9913, not9193.
Reference solution
Python
def maximumSwap(num: int) -> int:
digits = list(str(num))
last = {int(d): i for i, d in enumerate(digits)}
for i, d in enumerate(digits):
for bigger in range(9, int(d), -1):
if last.get(bigger, -1) > i:
j = last[bigger]
digits[i], digits[j] = digits[j], digits[i]
return int("".join(digits))
return numJava
public static int maximumSwap(int num) {
char[] digits = String.valueOf(num).toCharArray();
int[] lastIndex = new int[10];
for (int i = 0; i < 10; i++) lastIndex[i] = -1;
for (int i = 0; i < digits.length; i++) lastIndex[digits[i] - '0'] = i;
for (int i = 0; i < digits.length; i++) {
for (int d = 9; d > digits[i] - '0'; d--) {
if (lastIndex[d] > i) {
int j = lastIndex[d];
char t = digits[i];
digits[i] = digits[j];
digits[j] = t;
return Integer.parseInt(new String(digits));
}
}
}
return num;
}C++
int maximumSwap(int num) {
string digits = to_string(num);
vector<int> lastIndex(10, -1);
for (int i = 0; i < (int) digits.size(); i++) lastIndex[digits[i] - '0'] = i;
for (int i = 0; i < (int) digits.size(); i++) {
for (int d = 9; d > digits[i] - '0'; d--) {
if (lastIndex[d] > i) {
int j = lastIndex[d];
char t = digits[i];
digits[i] = digits[j];
digits[j] = t;
return stoi(digits);
}
}
}
return num;
}JavaScript
var maximumSwap = function(num) {
const digits = String(num).split("");
const lastIndex = new Array(10).fill(-1);
for (let i = 0; i < digits.length; i++) lastIndex[Number(digits[i])] = i;
for (let i = 0; i < digits.length; i++) {
for (let d = 9; d > Number(digits[i]); d--) {
if (lastIndex[d] > i) {
const j = lastIndex[d];
const t = digits[i];
digits[i] = digits[j];
digits[j] = t;
return parseInt(digits.join(""), 10);
}
}
}
return num;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 337 math problems · the whole catalogue
Learn the technique: Greedy Algorithms