Java, two pointers method, O(n) solution


  • 0
    C

    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)); 
        }
    

Log in to reply
 

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