Simple Java Solution: O(n)


  • 0
    J

    Step 1. Identify the first index (from left to right) where you can potentially make a swap.
    Step 2. Starting from the index found in Step 1 traverse towards right (i.e, towards least significant digit) and get the digit with max value in that range. The index of this max value would be the second index.
    Step 3. Swap the digits of the two indices.

    class Solution {
        public int maximumSwap(int num) {
            char[] arr = String.valueOf(num).toCharArray();
            
            int len = arr.length;
            
            if (len == 1) return num;
            
            char[] rev = String.valueOf(num).toCharArray();
            Arrays.sort(rev);
            
            int max = 0;
            
            int index1 = 0;
            int index2 = 0;
            
            for (int i = 0; i < len; i++) {
                int a = Integer.parseInt("" + arr[i]);
                if (arr[i] != rev[len - 1 - i]) {
                    index1 = i;
                    break;
                }
            }
            
            index2 = index1;
            
            max = Integer.parseInt("" + arr[index1]);
            
            for (int j = index1 + 1; j < len; j++) {
                int a = Integer.parseInt("" + arr[j]);
                if (a >= max) { //'>=' instead of '>' because if the occurance of the max is more than once 
                                //then take the index which is nearest to the LSD (Least Significant Digit) 
                    max = a;
                    index2 = j;
                }
            }
            
            if (index1 == index2) return num;
            
            char temp = arr[index1];
            arr[index1] = arr[index2];
            arr[index2] = temp;
            
            return Integer.parseInt(new String(arr));
        }
    }
    

Log in to reply
 

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