The basic idea is straightforward: for each digit `d`

in `num`

, we find the **maximum** and **rightmost** digit `m`

out of all digits to its right. Out of all these `(d, m)`

pairs, we need to find the leftmost one such that `d < m`

. Let `(ai, aj)`

be such a pair, then swapping digit `ai`

with digit `aj`

will yield the maximum number we can obtain.

How do we get the number after swapping? There is no need to convert the number to a string or char array, if we take advantage of the decomposition of decimal numbers. Any decimal number `a`

can be decomposed as follows: `a = sum(ak * 10^k)`

. If we swap two digits `ai`

and `aj`

, let the new number be `a'`

, then the difference between `a'`

and `a`

will be given by `a' - a = (aj - ai) * (10^i - 10^j)`

, which implies `a' = a + (aj - ai) * (10^i - 10^j)`

.

Finding `(ai, aj)`

can be done in one pass from the least significant digit up to the most significant digit of `num`

, as shown below. Here `d`

represents the current digit being examined and `m`

is the **maximum** and **rightmost** digit obtained so far before processing `d`

. If `d > m`

, this is not the pair we are looking for so we only update `m`

; else if `d < m`

, we find the leftmost `(d, m)`

pair with `d < m`

for now, so we update `(ai, aj)`

; for other cases we do nothing. Since we also need the multiplier for each digit to compute the new number, the program will keep track of these multipliers using variables like `fi`

, `fj`

, `fd`

, `fm`

. Time complexity is proportional to the number of digits in the input number `num`

while space complexity is constant.

```
public int maximumSwap(int num) {
int d = 0, fd = 1, m = 0, fm = 1;
int ai = 0, fi = 1, aj = 0, fj = 1;
for (int n = num; n != 0; n /= 10, fd *= 10) {
d = n % 10;
if (d > m) {
m = d; fm = fd;
} else if (d < m) {
ai = d; fi = fd;
aj = m; fj = fm;
}
}
return num + (aj - ai) * (fi - fj);
}
```