Solution: Maximum Swap

Statement

Given an integer num, return the maximum number that can be formed by swapping at least two digits once.

Constraints:

• $0 \leq$ num $\leq 10^5$

Solution

The problem involves maximizing a number by swapping two digits at most once. The key idea is to find a smaller digit on the left and a larger digit on the right that can be swapped to create the largest possible number. By scanning the digits from right to left, we can identify the optimal pair for swapping in a single pass, ensuring efficiency. This approach uses a greedy algorithm, as it makes the best possible decision at each step to maximize the number.

Here’s the step-by-step implementation of the solution:

1. Convert the input number to a string and then to a list of digits. This allows easy manipulation of individual digits.

2. Use the max_digit_index to track the index of the maximum digit encountered so far (starting from the right).

3. Use index_1 and index_2 to track the indices of the two digits to be swapped. Initially, set these to $-1$ to indicate no valid swap has been found.

4. Traverse the list of digits from the least significant (rightmost) to the most significant (leftmost). For each digit:

   1. If the current digit is greater than the digit on max_digit_index, update the max_digit_index to the current index.

   2. Otherwise, if it’s smaller, update index_1 and index_2 to potentially mark these digits to be swapped.

5. If both index_1 and index_2 have been updated (indicating a valid swap is found), swap the digits at these indices.

6. After the swap, convert the list of digits back to a string and then to an integer, which is returned as the result.

Let’s look at the following illustration to get a better understanding of the solution: