8ms Java solution with O(n) time and constant space


  • 0
    E

    Obviously, we only care about the left most position where the digit is smaller than the maximum of all digits to its right, hence the solution.

    class Solution {
        public int maximumSwap(int num) {
            int i = 1;
            int max = Integer.MIN_VALUE;
            int maxi = 0;
            int temp = num;
            int left = -1;
            int lefti = -1;
            int right = -1;
            int righti = -1;
            
            while (temp > 0) {
                int r = temp % 10;
                if (r > max) {
                    max = r;
                    maxi = i;
                } else if (r < max) {
                    left = r;
                    lefti = i;
                    right = max;
                    righti = maxi;
                }
                temp /= 10;
                i *= 10;
            }
            if (left != -1) {
                return num + (right - left) * (lefti - righti);
            }
            return num;
        }
    }
    

Log in to reply
 

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