# Java, two pointers method, O(n) solution

• Two pointers tech, left pointer search from left to right, locate the one at pos A that breaks the descending order. Then, right pointer search from end to A, find the max val.
Then left go back from A to start, find the closest one to the max val, swap them.

``````public int maximumSwap(int num) {

if (num <= 11) return num;

String str = String.valueOf(num);
char[] arr = str.toCharArray();
int left = 0;
int right = arr.length - 1;
int swapPos = left;

// locate the pos that max < current num, e.g., 98'5'6
while (left < arr.length){

if (arr[swapPos] < arr[left]) break;
swapPos = left;
left ++;
}

if (left >= arr.length) return num;

int max = arr[right];
int maxPos = right;

// from left to right, find the max val
while ( -- right > swapPos) {
if (arr[right] > max) {
max = arr[right];
maxPos = right;
}
}

// find the pos that should swap e.g., 98759 -->(find 8)
left = swapPos;
while (left >= 0) {
if (max > arr[left]) left --;
else break;
}

// compensate for --
left ++;

char tmp = arr[maxPos];
arr[maxPos] = arr[left];
arr[left] = tmp;

return Integer.valueOf(String.valueOf(arr));
}
``````

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