Solution
To make the resulting number biggest after one swap, we have to find the leftmost (most significant) digit which can be swapped. We would only want to swap a digit if there is a digit to the right of it which is greater than it. Consider the following numbers:
- 987: any swap will make the number smaller than before as there is no such digit which has a larger digit on right
- 897: swap 8 and 9
- 6790: This case gives us some more insight into the solution. There are 2 digits greater than 6 on the right of it - 7 and 9. Clearly, a number starting with 9 is greater than a number starting with 7. So we only want to swap the digit with the maximum number to its right. Hence, swap 6 and 9.
- 56949: Here, we have two option for swapping 5 with 9. The numbers will be 96549 and 96945. Clearly the latter number is bigger. This tells us that we want to swap digit 5 with the least significant occurrence of digit 9.
- 9867: swap 6 and 7
Algorithm:
- Start from the rightmost digit of the number.
- Keep track of the least significant occurrence of the maximum number encountered, maxNum.
- For each number, num, encountered, three cases:
- num > maxNum: update maxNum = num
- num < maxNum: this num can be swapped with the maxNum. We keep track of this using leftIdx and rightIdx (see code below)
- num = maxNum: do nothing as we only require the least significant occurrence of maxNum
- Swap the numbers (using leftIdx and rightIdx in code below)
int maximumSwap(int num) {
string temp = to_string(num);
int maxIdx, maxNum = 0, leftIdx=-1, rightIdx;
for (int i = temp.size()-1; i>=0; i--) {
int t = temp[i]-'0';
if (t > maxNum) {
maxNum = t;
maxIdx = i;
} else if (t < maxNum) {
leftIdx = i;
rightIdx = maxIdx;
}
}
if (leftIdx == -1)
return num;
swap(temp[leftIdx], temp[rightIdx]);
return stoi(temp);
}
Time complexity: O(n) where n is the number of digits in the number
Space complexity: O(1) as max number of digits = 8 as per constraint