Formatted question description: https://leetcode.ca/all/801.html
801. Minimum Swaps To Make Sequences Increasing
Level
Medium
Description
We have two integer sequences A
and B
of the same nonzero 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]
.
Solution
Use dynamic programming. Use countNoSwap
and countSwap
to represent the minimum number of swaps such that the current element is not swapped and the current element is swapped, respectively.
Let length
be the length of A
and B
. For i
from 1 to length  1
, check the values A[i  1]
, A[i]
, B[i  1]
and B[i]
. Let curCountNoSwap
and curCountSwap
be the minimum number of swaps at the current index, with the same meaning as countNoSwap
and countSwap
. Consider the following two cases. Both cases need to be considered for each index.
 When
A[i  1] < A[i]
andB[i  1] < B[i]
. If the numbers at indexi  1
are not swapped, the numbers at indexi
needn’t be swapped. If the numbers at indexi  1
are swapped, the numbers at indexi
need to be swapped as well. SocurCountNoSwap = Math.min(curCountNoSwap, countNoSwap)
andcurCountSwap = Math.min(curCountSwap, countSwap + 1)
.  When
A[i  1] < B[i]
andB[i  1] < A[i]
. Then either the numbers at indexi  1
need to be swapped or the numbers at indexi
need to be swapped. SocurCountNoSwap = Math.min(curCountNoSwap, countSwap)
andcurCountSwap = Math.min(curCountSwap, countNoSwap + 1)
.
After one index is visited, update countNoSwap = curCountNoSwap
and countSwap = curCountSwap
.
Finally, return the minimum of countNoSwap
and countSwap
.

class Solution { public int minSwap(int[] A, int[] B) { int countNoSwap = 0, countSwap = 1; int length = A.length; for (int i = 1; i < length; i++) { int curCountNoSwap = Integer.MAX_VALUE, curCountSwap = Integer.MAX_VALUE; if (A[i  1] < A[i] && B[i  1] < B[i]) { curCountNoSwap = Math.min(curCountNoSwap, countNoSwap); curCountSwap = Math.min(curCountSwap, countSwap + 1); } if (A[i  1] < B[i] && B[i  1] < A[i]) { curCountNoSwap = Math.min(curCountNoSwap, countSwap); curCountSwap = Math.min(curCountSwap, countNoSwap + 1); } countNoSwap = curCountNoSwap; countSwap = curCountSwap; } return Math.min(countNoSwap, countSwap); } }

// OJ: https://leetcode.com/problems/minimumswapstomakesequencesincreasing/ // Time: O(N) // Space: O(N) class Solution { int inf = 1e9; inline bool valid(vector<int>& A, vector<int>& B, int i) { return i == 0  (A[i] > A[i  1] && B[i] > B[i  1]); } unordered_map<int, int> memo; int dp(vector<int> &A, vector<int>& B, int i, bool swapped = false) { if (i == A.size()) return 0; int key = swapped * 2000 + i; if (memo.count(key)) return memo[key]; int cnt = valid(A, B, i) ? solve(A, B, i + 1, false) : inf; swap(A[i], B[i]); cnt = min(cnt, valid(A, B, i) ? 1 + solve(A, B, i + 1, true) : inf); swap(A[i], B[i]); return memo[key] = cnt; } public: int minSwap(vector<int>& A, vector<int>& B) { return dp(A, B, 0); } };

class Solution(object): def minSwap(self, A, B): """ :type A: List[int] :type B: List[int] :rtype: int """ N = len(A) keep = [float('inf')] * N swap = [float('inf')] * N keep[0] = 0 swap[0] = 1 for i in range(1, N): if A[i] > A[i  1] and B[i] > B[i  1]: keep[i] = keep[i  1] swap[i] = swap[i  1] + 1 if A[i] > B[i  1] and B[i] > A[i  1]: keep[i] = min(keep[i], swap[i  1]) swap[i] = min(swap[i], keep[i  1] + 1) return min(keep[N  1], swap[N  1])