801. Minimum Swaps To Make Sequences Increasing

/*
Refer: https://leetcode.com/problems/minimum-swaps-to-make-sequences-increasing/discuss/119835/Java-O(n)-DP-Solution
Time Complexity: O(N)
Space Complexity: O(1)

N = length of the A or B.
*/
class Solution {
    public int minSwap(int[] A, int[] B) throws IllegalArgumentException {
        if (A == null || B == null || A.length != B.length) {
            throw new IllegalArgumentException("Invalid input");
        }
        if (A.length <= 1) {
            return 0;
        }

        int swapRecord = 1;
        int fixRecord = 0;

        for (int i = 1; i < A.length; i++) {
            // if (Math.min(A[i-1], B[i-1]) >= Math.min(A[i], B[i])) {
            //     /*
            //     This case is true only if strictly increasing is not possible.
            //     This is only required if it is not guaranteed that the given input
            //     always makes it possible.
            //     */
            //     return -1;
            // }
            if (A[i-1] >= B[i] || B[i-1] >= A[i]) {
                /*
                A[1] >= B[2], which means the manipulation of A[2] & B[2] should
                be same as A[1] & B[1], if A[1] & B[1] swap, A[2] & B[2] should swap,
                vice versa.
                */
                swapRecord++;
            } else if (A[i-1] >= A[i] || B[i-1] >= B[i]) {
                /*
                A[1] >= A[2], which mean the manipulation of A[2] & B[2]
                and A[1] & B[1] should be opposite.
                */
                int temp = swapRecord;
                swapRecord = fixRecord + 1;
                fixRecord = temp;
            } else {
                /*
                Either swap or fix.. Both are OK. Thus find the previous minimum
                and set the new fix and swap counts.
                */
                int min = Math.min(fixRecord, swapRecord);
                fixRecord = min;
                swapRecord = min+1;
            }
        }

        return Math.min(swapRecord, fixRecord);
    }
}


/*
Time Complexity: O(N)
Space Complexity: O(N)

N = length of the A or B.
*/
class Solution {
    public int minSwap(int[] A, int[] B) throws IllegalArgumentException {
        if (A == null || B == null || A.length != B.length) {
            throw new IllegalArgumentException("Invalid input");
        }
        if (A.length <= 1) {
            return 0;
        }

        int[] swapRecord = new int[A.length];
        int[] fixRecord = new int[A.length];
        swapRecord[0] = 1;

        for (int i = 1; i < A.length; i++) {
            // if (Math.min(A[i-1], B[i-1]) >= Math.min(A[i], B[i])) {
            //     /*
            //     This case is true only if strictly increasing is not possible.
            //     This is only required if it is not guaranteed that the given input
            //     always makes it possible.
            //     */
            //     return -1;
            // }
            if (A[i-1] >= B[i] || B[i-1] >= A[i]) {
                /*
                A[1] >= B[2], which means the manipulation of A[2] & B[2] should
                be same as A[1] & B[1], if A[1] & B[1] swap, A[2] & B[2] should swap,
                vice versa.
                */
                fixRecord[i] = fixRecord[i-1];
                swapRecord[i] = swapRecord[i-1] + 1;
            } else if (A[i-1] >= A[i] || B[i-1] >= B[i]) {
                /*
                A[1] >= A[2], which mean the manipulation of A[2] & B[2]
                and A[1] & B[1] should be opposite.
                */
                fixRecord[i] = swapRecord[i-1];
                swapRecord[i] = fixRecord[i-1] + 1;
            } else {
                /*
                Either swap or fix.. Both are OK. Thus find the previous minimum
                and set the new fix and swap counts.
                */
                int min = Math.min(fixRecord[i-1], swapRecord[i-1]);
                fixRecord[i] = min;
                swapRecord[i] = min+1;
            }
        }

        return Math.min(swapRecord[A.length - 1], fixRecord[A.length - 1]);
    }
}