# 801. Minimum Swaps To Make Sequences Increasing

We have two integer sequences `A` and `B` of the same non-zero length.

We are allowed to swap elements `A[i]` and `B[i]`.  Note that both elements are in the same index position in their respective sequences.

At the end of some number of swaps, `A` and `B` are both strictly increasing.  (A sequence is *strictly increasing* if and only if `A[0] < A[1] < A[2] < ... < A[A.length - 1]`.)

Given A and B, return the minimum number of swaps to make both sequences strictly increasing.  It is guaranteed that the given input always makes it possible.

```
Example:
Input: A = [1,3,5,4], B = [1,2,3,7]
Output: 1
Explanation: 
Swap A[3] and B[3].  Then the sequences are:
A = [1, 3, 5, 7] and B = [1, 2, 3, 4]
which are both strictly increasing.
```

**Note:**

* `A, B` are arrays with the same length, and that length will be in the range `[1, 1000]`.
* `A[i], B[i]` are integer values in the range `[0, 2000]`.

{% hint style="info" %}
swap\[i]: the minimum swaps if A\[i] is swapped with B\[i] \
fix\[i]: the minimum swaps if A\[i] and B\[i] are fixed \
(1) if A\[i - 1] < A\[i] and B\[i - 1] < B\[i] and A\[i - 1] < B\[i] and B\[i - 1] < A\[i], swap\[i] = min(swap\[i - 1], fix\[i - 1]) + 1, fix\[i] = min(fix\[i - 1], swap\[i - 1]) \
(2) if A\[i - 1] >= B\[i] or B\[i - 1] >= A\[i], the manipulation of A\[i] and B\[i] should be same as the one of A\[i - 1] and B\[i - 1], swap\[i] = swap\[i - 1] + 1, fix\[i] = fix\[i - 1] \
(3) if A\[i - 1] >= A\[i] or B\[i - 1] >= B\[i], the manipulation of A\[i] and B\[i] should be opposite to the one of A\[i - 1] and B\[i - 1], swap\[i] = fix\[i - 1] + 1, fix\[i] = swap\[i - 1]
{% endhint %}

```cpp
// Dynamic Programming
int minSwap(vector<int>& A, vector<int>& B) { // time: O(n); space: O(n)
    int n = A.size();
    vector<int> swap(n), fix(n);
    swap[0] = 1;
    for (int i = 1; i < n; ++i) {
        if (A[i - 1] >= B[i] || B[i - 1] >= A[i]) { // (2) same as the previous manipulation
            swap[i] = swap[i - 1] + 1;
            fix[i] = fix[i - 1];
        } else if (A[i - 1] >= A[i] || B[i - 1] >= B[i]) { // (3) oppotite to the previous manipuliation
            swap[i] = fix[i - 1] + 1;
            fix[i] = swap[i - 1];
        } else { // (1) either swap or fix is okay
            int mn = min(swap[i - 1], fix[i - 1]);
            swap[i] = mn + 1;
            fix[i] = mn;
        }
    }
    return min(swap.back(), fix.back());
}
```

```cpp
// Space Optimized Dynamic Programming
int minSwap(vector<int>& A, vector<int>& B) { // time: O(n); space: O(1)
    int n = A.size(), swap = 1, fix = 0;
    for (int i = 1; i < n; ++i) {
        if (A[i - 1] >= B[i] || B[i - 1] >= A[i]) { // same as the previous manipulation
            swap = swap + 1;
            // fix = fix;
        } else if (A[i - 1] >= A[i] || B[i - 1] >= B[i]) { // oppotite to the previous manipuliation
            // int tmp = swap;
            // swap = fix + 1;
            // fix = tmp;
            std::swap(swap, fix);
            swap += 1;
        } else { // either swap or fix is okay
            int mn = min(swap, fix);
            swap = mn + 1;
            fix = mn;
        }
    }
    return min(swap, fix);
}
```

{% hint style="info" %}
下面是另外一種DP的想法，分為兩種情形，一種是(i - 1)和i位置上的數字已經排好序，如果要swap的話就一定要(i - 1)和i都swap; 另一種是(i - 1)和i位置上的數字在(i - 1)或i交換之後會變成有序增加。
{% endhint %}

```cpp
// Dynamic Programming
int minSwap(vector<int>& A, vector<int>& B) { // time: O(n); space: O(n)
    int n = A.size();
    vector<int> swap(n, n), fix(n, n);
    swap[0] = 1; 
    fix[0] = 0;
    for (int i = 1; i < n; ++i) {
        // Already increasing in [i - 1, i]
        if (A[i] > A[i - 1] && B[i] > B[i - 1]) {
            swap[i] = swap[i - 1] + 1;
            fix[i] = fix[i - 1];
        }
        // Will be increasing in [i - 1, i] after swapping (i - 1) or i
        if (A[i] > B[i - 1] && B[i] > A[i - 1]) {
            swap[i] = min(swap[i], fix[i - 1] + 1);
            fix[i] = min(fix[i], swap[i - 1]);
        }
    }
    return min(swap.back(), fix.back());
}
```

```cpp
// Dynamic Programming
int minSwap(vector<int>& A, vector<int>& B) { // time: O(n); space: O(1)
    int n = A.size(), swap1 = 1, fix1 = 0;
    for (int i = 1; i < n; ++i) {
        int swap2 = numeric_limits<int>::max(), fix2 = numeric_limits<int>::max();
        if (A[i] > A[i - 1] && B[i] > B[i - 1]) {
            swap2 = swap1 + 1;
            fix2 = fix1;
        }
        if (A[i] > B[i - 1] && B[i] > A[i - 1]) {
            swap2 = min(swap2, fix1 + 1);
            fix2 = min(fix2, swap1);
        }
        swap1 = swap2;
        fix1 = fix2;
    }
    return min(swap1, fix1);
}
```