Maximum Swap - Leetcode Solution

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:

1. We start by converting the given integer num to an array of digits.

2. We initialize two variables, max_index and swap_index to -1.

3. 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.

4. If such a digit exists, we update max_index to the index of the maximum digit, and swap_index to the current index.

5. 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.

6. Otherwise, we swap the digits at swap_index and max_index.

7. 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

1