670. Maximum Swap

2 pass

T: O(n)
S: O(n)

class Solution {
    private record Max(int idx, int val){};
    public int maximumSwap(int num) {
        String s = String.valueOf(num);
        int n = s.length();
        Max[] max = new Max[n];
        max[n-1] = new Max(n-1, s.charAt(n-1) - '0');
        for (int i = s.length()-2 ; i >= 0; i--) {
            if (max[i+1].val >= (s.charAt(i) - '0')) {
                max[i] = new Max(max[i+1].idx, max[i+1].val);
            } else {
                max[i] = new Max(i, (s.charAt(i) - '0'));
            }
        }

        int swapIdx1 = -1;
        int swapIdx2 = -1;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) - '0' < max[i].val) {
                swapIdx1 = i;
                swapIdx2 = max[i].idx;
                break;
            }
        }
        if (swapIdx1 == -1) {
            return num;
        }
        char[] c = s.toCharArray();
        char temp = c[swapIdx1];
        c[swapIdx1] = c[swapIdx2];
        c[swapIdx2] = temp;
        return Integer.parseInt(String.valueOf(c));
    }
}
/**
initial thought:
we want to put a max to the  small one from left
but how to find the max? and if it's 1999, we want the right most 9
so we can scan from right, to find the max idx 
and start from left to find a small number which is smaller than this max, and swap it!


2736
7766

6435
6555

1199
9999


1919
9999

2 pass -> build max array from right (idx, val)

2736
7766 -> max array

then compare from left, the first one num[i] < max[i] -> is the swap point

because in this case: 1199
we want to swap the right most max for the max value! so from right to build max array

also replace from left, so we can have the max number

T: O(n)
S: O(n)
 */

1 pass

T: O(n)
S: O(n)

class Solution {
    public int maximumSwap(int num) {
        String s = String.valueOf(num);
        char[] c = s.toCharArray();
        int max = -1;
        int maxIdx = -1;
        int swapIdx1 = -1;
        int swapIdx2 = -1;
        for (int i = s.length()-1; i >= 0; i--) {
            int cur = (c[i] - '0');
            if (cur > max) {
                max = cur;
                maxIdx = i;
            } else if (cur < max) {
                swapIdx1 = i;
                swapIdx2 = maxIdx;
            }
        }
        if (swapIdx1 == -1) {
            return num;
        }

        char temp = c[swapIdx1];
        c[swapIdx1] = c[swapIdx2];
        c[swapIdx2] = temp;
        return Integer.parseInt(String.valueOf(c));
    }
}

/**
T: O(n)
S: O(n)

actually we can do it for one pass.
Same from right to find max, 

and if there is a number < max, means it's a swap candidate
so we record it (swapIdx1 = i), also record the cur maxIdx to swapIdx2
swapIdx1 = i;
swapIdx2 = maxIdx;

in the end, just swap them

2736
   6
  x
 76
x


6435
   5
  s
 s   
6

max = 5 -> 6
max_i = 3 -> 0
when lower
swap_i = 1
swap_j = max_i = 3

swap 1 and 3
 */