801. Minimum Swaps To Make Sequences Increasing

Link

Solution

1. A[i - 1] < A[i] && B[i - 1] < B[i]. In this case, if we want to keep A and B increasing before the index i, can only have two choices. -> 1.1 don't swap at (i-1) and don't swap at i, we can get not_swap[i] = not_swap[i-1] -> 1.2 swap at (i-1) and swap at i, we can get swap[i] = swap[i-1]+1 if swap at (i-1) and do not swap at i, we can not guarantee A and B increasing.

2. A[i-1] < B[i] && B[i-1] < A[i] In this case, if we want to keep A and B increasing before the index i, can only have two choices. -> 2.1 swap at (i-1) and do not swap at i, we can get notswap[i] = Math.min(swap[i-1], notswap[i] ) -> 2.2 do not swap at (i-1) and swap at i, we can get swap[i]=Math.min(notswap[i-1]+1, swap[i])

  public int minSwap(int[] A, int[] B) {
        int n = A.length;
        int[] swap = new int[n];
        int[] noSwap = new int[n];
        swap[0] = 1;
        for(int i = 1; i < n; i++){
            swap[i] = noSwap[i] = n; //initial value for case 2 also satified case 1
            //case 1
            if(A[i] > A[i-1] && B[i] > B[i-1]){
                noSwap[i] = noSwap[i-1];
                swap[i] = swap[i-1] + 1;
            }
            //case 2, be ware that case 2 and case 1 can both be satified in some cases
            if(A[i] > B[i-1] && B[i] > A[i-1]){
                noSwap[i] = Math.min(swap[i-1], noSwap[i]);
                swap[i] = Math.min(noSwap[i-1] + 1, swap[i]);
            }
        }
        return Math.min(noSwap[n-1], swap[n-1]);
    }