Java easy to understand code with only two passes. Beats 87.77%


  • 2
    L

    Most of other solutions use a bucket to store the last occurrence of a digit and do a comparison for each digit. However, that is not efficient for case like "1000000"

    The idea is straightforward, as we can simply scan the digits backward and record the position of the largest digit when it first appears.

    Next time we scan the digits from left to right and find the first digit that is less than max to do the swap.

    class Solution {
        public int maximumSwap(int num) {
            char[] digits = String.valueOf(num).toCharArray();
            int[] maxIdx = new int[digits.length];
            int maxPos = digits.length - 1;
            maxIdx[maxPos] = maxPos;
            
            for (int i = digits.length - 2; i >= 0; i--) {
                if (digits[i] > digits[maxPos]) {
                    maxPos = i;
                }
                maxIdx[i] = maxPos;
            }
            
            for (int i = 0; i < digits.length; i++) {
                if (digits[i] != digits[maxIdx[i]]) {
                    char tmp = digits[i];
                    digits[i] = digits[maxIdx[i]];
                    digits[maxIdx[i]] = tmp;
                    return Integer.parseInt(String.valueOf(digits));
                }
            }
            
            return num;
        }
    }
    

  • 0
    Y

    How could you handle this case with second largest exchange : 92376 ?


  • 0
    L

    @yoyota from the first scan, the maxIdx array will be like: [0, 3, 3, 3, 4].
    Next time we scan from left to right, and at the second element, we find that digits[1] != digits[maxIdx[1]], so we know that we are good to swap the element at index 1 with the max element at index 3. In the end we get 97326


Log in to reply
 

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