Leetcode 801: Minimum Swaps To Make Sequences Increasing

https://leetcode.com/problems/minimum-swaps-to-make-sequences-increasing/description/

Notes:

This question is not easy.

One way to solve this question is dynamic programming. The key is to find the sub-state of the question. (or similar questions but with a smaller size).

This question is guaranteed to have a solution, which means that:

if A[i-1] >= A[i], then A[i-1] must < B[i];
if B[i-1] >= B[i], then B[i-1] must < A[i].

So there are only several valid situations:

1): A[i-1] < A[i] && A[i-1] < B[i] && B[i-1] < B[i] && B[i-1] < A[i]

in this case, we either swap the ith elements or not;

2): A[i-1] < A[i] && B[i-1] < B[i]

in this case, if we swap the (i-1)th element, then we need to swap the ith element as well;

3):  A[i-1] < B[i] && B[i-1] < A[i]

in this case, we need to either swap the ith elements or the (i-1)th elements.


If we use two one dimensional array to memorize the results up to ith element:

noSwap[i]: represents the minimum of swaps up to the ith element, with the ith one not swapped.
swap[i]: represents the minimum of swaps up to the ith element, with the ith one swapped;

(For each element, it can either swap or not swap, as long as it can make the two sequence increasing)

The transition formulas for the above situations are:

1):  noswap[i] = min(noswap[i-1], swap[i-1]);
      swap[i] = min(noswap[i-1], swap[i-1]) + 1;

2):  noswap[i] = noswap[i-1];
       swap[i] = swap[i-1] + 1;

3):   noswap[i] = swap[i-1];
       swap[i] = noswap[i-1] + 1;

The T-C is O(N), and the S-C is O(N) too.

See the code below:

class Solution {
public:
    int minSwap(vector<int>& A, vector<int>& B) {
        int n = A.size();
        vector<int> noSwap(n, n), swap(n, n);
        noSwap[0] = 0;
        swap[0] = 1;
        for(int i=1; i<n; ++i) {
            if(A[i-1] < A[i] && A[i-1] < B[i] && B[i-1] < B[i] && B[i-1] < A[i]) {
                noSwap[i] = min(noSwap[i-1], swap[i-1]);
                swap[i] = min(noSwap[i-1], swap[i-1]) + 1;
            }
            else if(A[i-1] < A[i] && B[i-1] < B[i]) {
                noSwap[i] = noSwap[i-1];
                swap[i] = swap[i-1] + 1;
            }
            else {
                noSwap[i] = swap[i-1];
                swap[i] = noSwap[i-1] + 1;
            }
        }
        return min(noSwap[n-1], swap[n-1]);
    }
};

From the above code, we can see that dp[i] is derived from dp[i-1] only. This means that we can further optimize the space complexity to O(1).

See the code below:

class Solution {
public:
    int minSwap(vector<int>& A, vector<int>& B) {
        int pre_noSwap = 0, pre_swap = 1;
        for(int i=1; i<A.size(); ++i) {
            int cur_noSwap = 0, cur_swap = 1;
            if(A[i-1] < A[i] && A[i-1] < B[i] && B[i-1] < B[i] && B[i-1] < A[i]) {
                cur_noSwap = min(pre_noSwap, pre_swap);
                cur_swap = min(pre_noSwap, pre_swap) + 1;
            }
            else if(A[i-1] < A[i] && B[i-1] < B[i]) {
                cur_noSwap = pre_noSwap;
                cur_swap = pre_swap + 1;
            }
            else {
                cur_noSwap = pre_swap;
                cur_swap = pre_noSwap + 1;
            }
            pre_noSwap = cur_noSwap;
            pre_swap = cur_swap;
        }
        return min(pre_noSwap, pre_swap);
    }
};