Maximum Swap
Understanding the Problem
We have a non-negative integer, and we can swap two of its digits at most once to make the number as large as possible. If the number is already the largest it can be, we leave it alone.
Digit placement drives the value. A larger digit earlier in the number contributes far more to the total than the same digit later, because each position to the left carries a higher power of ten. So we want to find the leftmost digit that has a bigger digit somewhere to its right, and swap it with the largest such digit. When that larger digit appears more than once, we swap with its rightmost occurrence. That keeps the bigger digit at the same left position while pushing the displaced smaller digit as far right as possible, where it costs the least.
With num = 1993, the digit 1 at position 0 has a 9 to its right. There are two 9s, at positions 1 and 2. We swap with the last 9 (position 2), giving 9913. Swapping with either 9 puts a 9 at the front, but swapping with the later one leaves a 9 at position 1 instead of a 1.
Key Constraints:
0 <= num <= 10^8means the number has at most 9 digits. With d <= 9, even an O(d^2) brute force over digit pairs (at most 36 pairs) runs instantly. The difficulty here is getting the tie-breaking correct, not the running time.
Approach 1: Brute Force (Try All Swaps)
Intuition
Try every possible pair of positions to swap, compute the resulting number, and keep the maximum. With at most 9 digits, the number of pairs is at most C(9, 2) = 36, so checking all of them is cheap.
For each pair (i, j), swap the digits, convert back to a number, compare against the running maximum, then swap back to restore the array for the next pair.
Algorithm
- Convert the number to a character array (or string of digits).
- Initialize
maxNum = num(the original number, in case no swap helps). - For each pair of indices
iandjwherei < j: - Swap
digits[i]anddigits[j]. - Convert the array back to a number.
- Update
maxNumif this number is larger. - Swap back to restore the original array.
- Return
maxNum.
Visualization and Code
Loading animation...
- Time Complexity: O(d^3), where d is the number of digits (at most 9). There are d*(d-1)/2 pairs, which is O(d^2), and converting the array back to a number for each pair is O(d). With d <= 9 this is effectively constant time.
- Space Complexity: O(d). We store the digit array, which has at most 9 characters.
The brute force ignores the structure of the problem. The next approach uses the fact that a larger digit belongs as far left as possible to pick the single best swap in one pass.
Approach 2: Greedy (Last Occurrence Array)
Intuition
To maximize the number, we want the largest available digit as far left as possible. Scan from left to right, and at each position check whether a bigger digit appears anywhere to its right. The first position where that holds is the one to fix: we have only one swap, so spending it on the most significant improvable position gives the largest gain. Once we make that swap, we return.
When the bigger digit appears more than once to the right, we swap with its rightmost occurrence. Consider 27939. At position 0 the digit is 2, and 9 appears at positions 2 and 4. Swapping with position 4 gives 97932; swapping with position 2 gives 97239. Both put a 9 at the front, but the rightmost choice leaves the displaced 2 at position 4, where it contributes least.
The algorithm: precompute the last occurrence of each digit (0-9), then scan left to right. At each position, check whether any digit strictly larger than the current one has its last occurrence to the right. If so, swap and return.
Let i be the leftmost position where some larger digit appears to the right. Any number that improves on the original must raise some position, and raising any position to the right of i produces a smaller number than raising i, since i carries a higher power of ten. So the optimal swap must raise position i. To raise it as much as possible, we bring in the largest digit available to the right, which is why we scan d from 9 downward. Among equal copies of that digit, swapping with the rightmost copy leaves digits[i] displaced to the furthest-right slot, which is the least valuable position the displaced digit can occupy.
Algorithm
- Convert the number to a character array.
- Create an array
lastIndexof size 10 (for digits 0-9), storing the last position where each digit appears. - Scan the digit array from left to right. At each position
i: - Check digits 9 down to
digits[i] + 1(strictly larger digits). - If
lastIndex[d]is greater thani, swapdigits[i]withdigits[lastIndex[d]]. - Convert back to a number and return immediately.
- If no swap was made, the number is already maximized. Return it as-is.
Visualization and Code
Loading animation...
- Time Complexity: O(d). We make one pass to build the
lastIndexarray (O(d)), then scan left to right (O(d)). At each position, we check at most 10 digits, which is O(1). So the total is O(d), where d is the number of digits. - Space Complexity: O(d). We store the digit array (O(d)) and the
lastIndexarray (O(10) = O(1)). The dominant space cost is the digit array.