Java O(N) solution with recursive call


  • 0
    J
    class Solution {
        // The idea is : find the max digit, if the max digit is not at left-most position (MSB), then we swap it with the most signicant digit.
        // Saying 1798 -> max digit is 9, and swap it with the digit at left most position, and get 9718. if the max digit is equal to the left-most digit, no need to swap them and we just recursivly call to get max value out of [startIndex+1, endIndex]
        public int maximumSwap(int num) {
            char[] digits = Integer.toString(num).toCharArray();
            maxSwap(digits, 0);
            return Integer.valueOf(new String(digits));
        }
        
        // digits: MSB first
        // in place update
        private void maxSwap(char[] digits, int start){
            if(start >= digits.length){
                return;
            }
            char maxDigit = 0;
            int maxIndex = 0;
            for(int i = start; i < digits.length; i++){
                // here if we have duplicate max digit, we should use the right-most digit. 
                // Saying 1998, we should swap the right-most 9 and get max 9918.  If we swap the first 9, we got 9198 which is not the answer.
                if(digits[i] >= maxDigit){
                    maxDigit = digits[i];
                    maxIndex = i;
                }
            }
            // if max index is at start (9354) or max value is equal to start value (9198)
            if(maxDigit == digits[start]){
                maxSwap(digits, start + 1); 
            }
            else{
                //swap start and maxIndex
                char temp = digits[start];
                digits[start] = digits[maxIndex];
                digits[maxIndex] = temp;
            }
        }
    }
    

Log in to reply
 

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