Java simple solution, O(n) time

• Use buckets to record the last position of digit 0 ~ 9 in this num.

Loop through the num array from left to right. For each position, we check whether there exists a larger digit in this num (start from 9 to current digit). We also need to make sure the position of this larger digit is behind the current one. If we find it, simply swap these two digits and return the result.

``````class Solution {
public int maximumSwap(int num) {
char[] digits = Integer.toString(num).toCharArray();

int[] buckets = new int[10];
for (int i = 0; i < digits.length; i++) {
buckets[digits[i] - '0'] = i;
}

for (int i = 0; i < digits.length; i++) {
for (int k = 9; k > digits[i] - '0'; k--) {
if (buckets[k] > i) {
char tmp = digits[i];
digits[i] = digits[buckets[k]];
digits[buckets[k]] = tmp;
return Integer.valueOf(new String(digits));
}
}
}

return num;
}
}
``````

• @joeztang What an amazing solution it is!! So brilliant !
Easy understanding solution. Voted up!

• The idea to use buckets to store the last occurrence indices is so damn imaginative!

• ``````   for (int i = 0; i < digits.length; i++) {
for (int k = 9; k > digits[i] - '0'; k--) {
if (buckets[k] > i) {
char tmp = digits[i];
digits[i] = digits[buckets[k]];
digits[buckets[k]] = tmp;
return Integer.valueOf(new String(digits));
}
}
}
``````

This loop can be further optimized. As written it's a 10*n runtime, but the inner loop doesn't need to start from 9 for all digits. With '8745' as an example, when we first consider 8, we've already concluded there's no 9 to its right, so when considering 7, we don't need to check 9 again.

``````    max = 9
for (int i = 0; i < digits.length; i++) {
for (int k = max; k > digits[i] - '0'; k--) {
if (buckets[k] > i) {
char tmp = digits[i];
digits[i] = digits[buckets[k]];
digits[buckets[k]] = tmp;
return Integer.valueOf(new String(digits));
}
}
max = digits[i] - '0';
}
``````

With this, each number is considered at most once without generating a solution, making the running time 1*n.

• A minor improvement as we could infer the update digit from k, so the inner swap logic does not require a tmp variable here:

``````   for (int i = 0; i < digits.length; i++) {
for (int k = 9; k > digits[i] - '0'; k--) {
if (buckets[k] > i) {
digits[buckets[k]] = digits[i];
digits[i] = (char)(k + '0');
return Integer.valueOf(new String(digits));
}
}
}``````

• It's really o(n) time? ,the double for loop is not o (n)time

• @CP_UESTC Because the iteration time of the second loop will be at most 9 times which can be regarded as constant time.

• This post is deleted!

• One pass, no buckets:

``````        char[] ca = Integer.toString(num).toCharArray();
int from = -1, to = -1;
for (int i = 1; i < ca.length; ++i) {
if (from < 0 && ca[i] > ca[i - 1]) {
from = i - 1;
to = i;
}
for (int j = from - 1; j >= 0 && ca[i] > ca[j]; --j) from = j;
if (to >= 0 && ca[i] >= ca[to]) to = i;
}
if (from >= 0) {
char tmp = ca[from];
ca[from] = ca[to];
ca[to] = tmp;
}
return Integer.parseInt(new String(ca));
``````

• I like this idea, thanks!

• Very good idea!

• Amazing solution!

• This is O(n^2), isn't it? The given number is in the range [0, 10^8], so the number of digits n is 8, and the loop with inner loop's time complexity is O(n*9) worst case, which should be O(n^2) as 9 is even greater than 8.

Please correct me where is wrong with my analysis.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.