Maximum Swap — Leetcode 670

Original problem link: https://leetcode.com/problems/maximum-swap/description/

In this problem, we’re asked to swap two digits in an integer at most once to find the maximum value after swapping.

I noticed a couple of things. First, if a number’s digits is in a non-increasing sequence, there is no swap needed. Second, for a digit sequence where a swap is needed, the best swap is to 1) find the max digit after the sequence starts increasing and 2) swap that digit with the leftmost digit in the non-increasing part of the sequence that is smaller than the max digit.

This code is O(n) and beats 100% of submissions (0 ms runtime).

class Solution {
    public int maximumSwap(int num) {
        String val = String.valueOf(num);
        char[] array = val.toCharArray();

        // find where the digits start increasing, since descending sequences don't need swapping
        int i = 0;
        while (i < array.length - 1 && array[i] >= array[i + 1]) {
            i++;
        }

        if (i == array.length - 1) {
            // whole number has descending digits so no swaps needed
            return num;
        }

        // find max after the digits start increasing
        int j = i + 1;
        char max = '0';
        int maxIndex = j;
        while (j < array.length) {
            if (max <= array[j]) {
                max = array[j];
                maxIndex = j;
            }
            j++;
        }
        
        // find correct first index to swap, which is the leftmost digit in descending part of number that is smaller than the digit at maxIndex
        int firstIndex = 0;
        for (int k = 0; k <= i; k++) {
            if (array[k] < array[maxIndex]) {
                firstIndex = k;
                break;
            }
        }

        // swap
        char temp = array[firstIndex];
        array[firstIndex] = array[maxIndex];
        array[maxIndex] = temp;

        return Integer.valueOf(new String(array));
    }
}

My initial idea was to sort a copy of the char array first, then swap the first mismatching digit and find the most appropriate index to switch it with. But since it is O(n log n), it is slightly slower (1–3 ms).

class Solution {
    public int maximumSwap(int num) {
        String val = String.valueOf(num);
        Character[] array = new Character[val.length()];
        for (int i = 0; i < val.length(); i++) {
            array[i] = val.charAt(i);
        }
        Arrays.sort(array, (x, y) -> Character.compare(y, x));

        char[] result = val.toCharArray();
        for (int i = 0; i < val.length(); i++) {
            if (array[i] != val.charAt(i)) {
                for (int j = val.length() - 1; j > i; j--) {
                    if (val.charAt(j) == array[i] && val.charAt(j) != array[j]) {
                        // swap i and j
                        result[j] = val.charAt(i);
                        result[i] = val.charAt(j);
                        break;
                    }
                }
                break;
            }
        }

        return Integer.valueOf(new String(result));
    }
}