• Time:O(n)
• Space:O(n)

C++

``````class Solution {
public:
int minSwap(vector<int>& A, vector<int>& B) {
vector<int> keepAt(A.size(), INT_MAX);
vector<int> swapAt(A.size(), INT_MAX);
keepAt[0] = 0;
swapAt[0] = 1;

for (int i = 1; i < A.size(); ++i) {
if (A[i] > A[i - 1] && B[i] > B[i - 1]) {
keepAt[i] = keepAt[i - 1];
swapAt[i] = swapAt[i - 1] + 1;
}
if (A[i] > B[i - 1] && B[i] > A[i - 1]) {
keepAt[i] = min(keepAt[i], swapAt[i - 1]);
swapAt[i] = min(swapAt[i], keepAt[i - 1] + 1);
}
}

return min(keepAt.back(), swapAt.back());
}
};
``````

JAVA

``````class Solution {
public int minSwap(int[] A, int[] B) {
final int n = A.length;

int[] keepAt = new int[n];
int[] swapAt = new int[n];
Arrays.fill(keepAt, Integer.MAX_VALUE);
Arrays.fill(swapAt, Integer.MAX_VALUE);
keepAt[0] = 0;
swapAt[0] = 1;

for (int i = 1; i < n; ++i) {
if (A[i] > A[i - 1] && B[i] > B[i - 1]) {
keepAt[i] = keepAt[i - 1];
swapAt[i] = swapAt[i - 1] + 1;
}
if (A[i] > B[i - 1] && B[i] > A[i - 1]) {
keepAt[i] = Math.min(keepAt[i], swapAt[i - 1]);
swapAt[i] = Math.min(swapAt[i], keepAt[i - 1] + 1);
}
}

return Math.min(keepAt[n - 1], swapAt[n - 1]);
}
}
``````

Python

``````class Solution:
def minSwap(self, A: List[int], B: List[int]) -> int:
keepAt = [math.inf] * len(A)
swapAt = [math.inf] * len(A)
keepAt[0] = 0
swapAt[0] = 1

for i in range(1, len(A)):
if A[i] > A[i - 1] and B[i] > B[i - 1]:
keepAt[i] = keepAt[i - 1]
swapAt[i] = swapAt[i - 1] + 1
if A[i] > B[i - 1] and B[i] > A[i - 1]:
keepAt[i] = min(keepAt[i], swapAt[i - 1])
swapAt[i] = min(swapAt[i], keepAt[i - 1] + 1)

return min(keepAt[-1], swapAt[-1])
``````

• Time:O(n)
• Space:O(1)

C++

``````class Solution {
public:
int minSwap(vector<int>& A, vector<int>& B) {
int keepAt = 0;
int swapAt = 1;
int prevKeepAt = 0;
int prevSwapAt = 1;

for (int i = 1; i < A.size(); ++i) {
keepAt = INT_MAX;
swapAt = INT_MAX;
if (A[i] > A[i - 1] && B[i] > B[i - 1]) {
keepAt = prevKeepAt;
swapAt = prevSwapAt + 1;
}
if (A[i] > B[i - 1] && B[i] > A[i - 1]) {
keepAt = min(keepAt, prevSwapAt);
swapAt = min(swapAt, prevKeepAt + 1);
}
prevKeepAt = keepAt;
prevSwapAt = swapAt;
}

return min(keepAt, swapAt);
}
};
``````

JAVA

``````class Solution {
public int minSwap(int[] A, int[] B) {
int keepAt = 0;
int swapAt = 1;
int prevKeepAt = 0;
int prevSwapAt = 1;

for (int i = 1; i < A.length; ++i) {
keepAt = Integer.MAX_VALUE;
swapAt = Integer.MAX_VALUE;
if (A[i] > A[i - 1] && B[i] > B[i - 1]) {
keepAt = prevKeepAt;
swapAt = prevSwapAt + 1;
}
if (A[i] > B[i - 1] && B[i] > A[i - 1]) {
keepAt = Math.min(keepAt, prevSwapAt);
swapAt = Math.min(swapAt, prevKeepAt + 1);
}
prevKeepAt = keepAt;
prevSwapAt = swapAt;
}

return Math.min(keepAt, swapAt);
}
}
``````