Algorithm
Problem Name: 670. Maximum Swap
Problem Link: https://leetcode.com/problems/maximum-swap/
You are given an integer num. You can swap two digits at most once to get the maximum valued number.
Return the maximum valued number you can get.
Example 1:
Input: num = 2736 Output: 7236 Explanation: Swap the number 2 and the number 7.
Example 2:
Input: num = 9973 Output: 9973 Explanation: No swap.
Constraints:
0 <= num <= 108
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int maximumSwap(int num) {
string s = to_string(num);
for(int i = 0; i < s.size(); i++){
int digit = s[i] - '0';
int index = i;
for(int j = s.size() - 1; j > i; j--){
if(s[j] - '0' > digit){
digit = s[j] - '0';
index = j;
}
}
if(digit != s[i] - '0'){
swap(s[i], s[index]);
return stoi(s);
}
}
return num;
}
};
Input
num = 2736
Output
7236
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int maximumSwap(int num) {
String stringValue = Integer.toString(num);
Map < Integer, Integer> valToIndexMap = new HashMap<>();
int[] digits = new int[String.valueOf(num).length()];
for (int i = digits.length - 1; i >= 0; i--) {
int digit = num % 10;
num /= 10;
digits[i] = digit;
valToIndexMap.putIfAbsent(digit, i);
}
for (int i = 0; i < digits.length; i++) {
for (int k = 9; k > digits[i]; k--) {
if (valToIndexMap.getOrDefault(k, -1) > i) {
int swapIndex = valToIndexMap.get(k);
return Integer.parseInt(
stringValue.substring(0, i) // Digits before swap index
+ k // Swapped value
+ stringValue.substring(i + 1, swapIndex) // Digits after original index(i) and before swappedIndex
+ digits[i] // Digit at original index(i)
+ ((swapIndex + 1) != stringValue.length() // Check if swapIndex is last digit of num
? stringValue.substring(swapIndex + 1) // If not then add digits that come after the swapIndex
: "")); // Else add an empty string
}
}
}
return Integer.parseInt(stringValue);
}
}
Input
num = 2736
Output
7236
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const maximumSwap = function(num) {
const arr = ('' + num).split('')
for(let i = 0; i < arr.length - 1; i++) {
let cur = +arr[i]
let nextMax = Math.max(...arr.slice(i+1).map(el => +el))
if (nextMax > cur) {
let idx = arr.lastIndexOf(''+nextMax)
arr[i] = nextMax
arr[idx] = cur
break
}
}
return +(arr.join(''))
};
Input
num = 9973
Output
9973
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def maximumSwap(self, num):
res, num = num, list(str(num))
for i in range(len(num) - 1):
for j in range(i + 1, len(num)):
if int(num[j]) > int(num[i]):
tmp = int("".join(num[:i] + [num[j]] + num[i + 1:j] + [num[i]] + num[j + 1:]))
if tmp > res: res = tmp
return res
Input
num = 9973
Output
9973