1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

$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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.