Similar Problems
Similar Problems not available
Maximum Swap - Leetcode Solution
LeetCode: Maximum Swap Leetcode Solution
Difficulty: Medium
Problem:
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
Solution:
To solve this problem, we can first convert the given integer num into an array of digits. Then, we can iterate over the digits from left to right and check if there exists any digit greater than the current digit to the right of it. If such a digit exists, we can simply swap the current digit with the maximum digit to its right.
However, if there are multiple digits greater than the current digit to its right, we should swap with the rightmost digit as this would produce the maximum number.
Algorithm:
-
We start by converting the given integer num to an array of digits.
-
We initialize two variables, max_index and swap_index to -1.
-
We iterate over the digits from left to right, and for each digit, we check if there exists any digit greater than it to its right.
-
If such a digit exists, we update max_index to the index of the maximum digit, and swap_index to the current index.
-
After the loop, we check if swap_index is still -1. If it is, it means no swap is required, and we return the given integer num.
-
Otherwise, we swap the digits at swap_index and max_index.
-
We join the array of digits back into an integer and return it.
Code:
Here is the Python code implementing the above algorithm:
def maximumSwap(num: int) -> int: digits = [int(d) for d in str(num)]
max_index = -1
swap_index = -1
for i in range(len(digits) - 1):
if digits[i] < digits[i+1]:
max_index = i+1
swap_index = i
if swap_index == -1:
return num
max_digit = max(digits[max_index:])
for i in range(len(digits) - 1, swap_index, -1):
if digits[i] == max_digit:
max_index = i
break
digits[swap_index], digits[max_index] = digits[max_index], digits[swap_index]
return int(''.join([str(d) for d in digits]))
#Sample Input num = 2736
print(maximumSwap(num))
#Output: 7236
#Sample Input num = 9973
print(maximumSwap(num))
#Output: 9973
Maximum Swap Solution Code
1class Solution {
2public:
3 int maximumSwap(int num) {
4 // Convert num to string
5 string numStr = to_string(num);
6
7 // Initialize max swap to 0
8 int maxSwap = 0;
9
10 // Iterate through string
11 for (int i = 0; i < numStr.length(); i++) {
12 // Iterate through string again starting from end
13 for (int j = numStr.length() - 1; j > i; j--) {
14 // If the current digit is less than the digit we're checking
15 if (numStr[i] < numStr[j]) {
16 // Swap the digits
17 swap(numStr[i], numStr[j]);
18
19 // Convert the string back to an int and compare to max swap
20 int temp = stoi(numStr);
21 maxSwap = max(maxSwap, temp);
22
23 // Swap the digits back
24 swap(numStr[i], numStr[j]);
25 }
26 }
27 }
28
29 return maxSwap;
30 }
31};