# Minimum number of swaps to make two arrays strictly increasing

I'm trying to understand the solution of the following problem (LC 801):

Given two arrays, A and B, of the same nonzero length, find the minimum number of swaps (A[i] <--> B[i]) to make A and B strictly increasing.

The solution is guaranteed to exist for the given input data.

Example:

Input: A = [1, 2, 9, 4, 5, 6], B = [7, 8, 3, 10, 12, 13]

Output: 1 (swap 9 and 3)

The solutions posted by others consider a dp array, of size [2, A.size()], which is filled as follows:

int N = static_cast<int>(A.size());
std::vector<std::vector<int>> dp(2, std::vector<int>(N, N));

for (int ii = 1; ii < N; ++ii) {
if (A[ii - 1] > A[ii] && B[ii - 1] > B[ii]) {
dp[0][ii] = std::min(dp[0][ii], dp[0][ii - 1]);
dp[1][ii] = std::min(dp[1][ii], dp[1][ii - 1] + 1);
}
if (A[ii] > B[ii - 1] && B[ii] > A[ii - 1]) {
dp[0][ii] = std::min(dp[0][ii], dp[1][ii - 1]);
dp[1][ii] = std::min(dp[1][ii], dp[0][ii - 1] + 1);
}
}

return std::min(dp[0][N - 1], dp[1][N - 1]);


How to think / develop the idea for the solution?

It is clear that in the case the monotony is broken, i.e. A[ii] <= A[ii - 1] we need to swap, but, from trying a few test cases, this is not the optimal way to do the swaps.

$$dp[b][i]$$ denotes the minimum number of swaps needed to make the first $$i$$ elements of both arrays strictly increasing where $$b$$ is a boolean flag denoting whether we've swapped $$A[i]$$ and $$B[i]$$ (or $$\infty$$ if this minimum doesn't exist).
The key observation is that we only care about what $$A[i-1]$$ and $$B[i-1]$$ are when calculating $$dp[0/1][i]$$. This means that we can calculate $$dp[0/1][i]$$ using only $$A[i-1]$$, $$B[i-1]$$, $$A[i]$$, $$B[i]$$ and $$dp[0/1][i-1]$$ in $$\mathcal O(1)$$ time. (The recurrences are shown in the code you posted).
The answer is clearly $$\min(dp[0/1][N])$$, and this solution runs in $$\mathcal O(N)$$ time.