Problem Description

Given two integer arrays A and B of the same length, your task is to make both sequences strictly increasing by swapping elements at the same index (i.e., swap A[i] with B[i] for any i). You can choose to swap or not at each index, but you must ensure that after all swaps, both arrays are strictly increasing:

• A[0] < A[1] < ... < A[n-1]
• B[0] < B[1] < ... < B[n-1]

Return the minimum number of swaps required to achieve this. It is guaranteed that there is always at least one valid solution.

Constraints:

• 1 ≤ A.length = B.length ≤ 1000
• 0 ≤ A[i], B[i] <= 2000
• There is always at least one way to make both sequences strictly increasing.

Thought Process

At first glance, the problem suggests checking all possible combinations of swaps, but with arrays up to length 1000, brute-force is not feasible due to the exponential number of possibilities.

Instead, we observe that at each index, we have two choices: swap or not swap. Our decision at each step affects future decisions because the sequences must remain strictly increasing. Thus, we need to keep track of two states at each index:

• The minimum swaps needed if we do not swap at the current index.
• The minimum swaps needed if we do swap at the current index.

By keeping track of these two states, we can use dynamic programming to efficiently find the minimum number of swaps required.

Solution Approach

We use dynamic programming to solve the problem efficiently. Here’s the step-by-step breakdown:

1. Define State:
   • keep[i]: The minimum swaps needed to make sequences increasing up to index i without swapping at i.
   • swap[i]: The minimum swaps needed up to index i with a swap at i.
2. Initialize:
   • At index 0, if we don’t swap, swaps = 0 (keep[0] = 0).
   • If we swap at index 0, swaps = 1 (swap[0] = 1).
3. Transition:
   • For each index i from 1 to n-1, check two conditions:
     • A[i] > A[i-1] and B[i] > B[i-1]: No swap needed at i if previous was not swapped, or swap at i if previous was swapped.
     • A[i] > B[i-1] and B[i] > A[i-1]: Current swap status can be the opposite of previous (swap or not swap).
   • Update keep[i] and swap[i] accordingly, taking the minimum swaps for each possibility.
4. Result:
   • The answer is min(keep[n-1], swap[n-1]), the minimal swaps required at the last index.

This approach only needs to store the previous state, so we can optimize space to O(1) by using two variables instead of arrays.

Example Walkthrough

Example:
A = [1, 3, 5, 4]
B = [1, 2, 3, 7]

1. Index 0:
   No swap: keep[0] = 0
   Swap: swap[0] = 1
2. Index 1:
   A[1]=3 > A[0]=1 and B[1]=2 > B[0]=1 so both sequences are increasing without swap.
   keep[1] = keep[0] = 0 (no swap at 1)
   swap[1] = swap[0] + 1 = 2 (swap at both 0 and 1)
   Also, A[1]=3 > B[0]=1 and B[1]=2 > A[0]=1 so swapping only at 1 is possible:
   swap[1] = min(swap[1], keep[0] + 1) = min(2, 1) = 1
keep[1] = min(keep[1], swap[0]) = min(0, 1) = 0
3. Index 2:
   A[2]=5 > A[1]=3 and B[2]=3 > B[1]=2 so
   keep[2] = keep[1] = 0
swap[2] = swap[1] + 1 = 2
A[2]=5 > B[1]=2 and B[2]=3 > A[1]=3 (false, 3 is not greater than 3), so no update here.
4. Index 3:
   A[3]=4 > A[2]=5 is false, so no update for keep.
   A[3]=4 > B[2]=3 and B[3]=7 > A[2]=5 is true, so we can swap at 3 if we didn't swap at 2.
   swap[3] = min(swap[3], keep[2] + 1) = min(inf, 1) = 1
keep[3] = min(keep[3], swap[2]) = min(inf, 2) = 2
5. Result:
   min(keep[3], swap[3]) = min(2, 1) = 1

Thus, only 1 swap is needed (at index 3).

Time and Space Complexity

• Brute-force:
  • Time: O(2^n), since each index has two choices (swap or not), leading to exponential growth.
  • Space: O(n) for recursion stack.
• Optimized DP Approach:
  • Time: O(n), because we process each index once and do constant work per index.
  • Space: O(1), since we only need to keep track of two variables (previous swap and keep).

Summary

The key insight is that at each index, the decision to swap or not depends only on the previous state. By using dynamic programming to track the minimum swaps needed for both cases (swap, no swap), we efficiently compute the answer in linear time. This approach elegantly avoids brute-force enumeration and leverages the problem's sequential structure for optimal performance.

Code Implementation

class Solution:
    def minSwap(self, A, B):
        n = len(A)
        keep = 0
        swap = 1
        for i in range(1, n):
            keep2 = swap2 = float('inf')
            if A[i] > A[i-1] and B[i] > B[i-1]:
                keep2 = min(keep2, keep)
                swap2 = min(swap2, swap + 1)
            if A[i] > B[i-1] and B[i] > A[i-1]:
                keep2 = min(keep2, swap)
                swap2 = min(swap2, keep + 1)
            keep, swap = keep2, swap2
        return min(keep, swap)
      

class Solution {
public:
    int minSwap(vector<int>& A, vector<int>& B) {
        int n = A.size();
        int keep = 0, swap = 1;
        for (int i = 1; i < n; ++i) {
            int keep2 = INT_MAX, swap2 = INT_MAX;
            if (A[i] > A[i-1] && B[i] > B[i-1]) {
                keep2 = min(keep2, keep);
                swap2 = min(swap2, swap + 1);
            }
            if (A[i] > B[i-1] && B[i] > A[i-1]) {
                keep2 = min(keep2, swap);
                swap2 = min(swap2, keep + 1);
            }
            keep = keep2;
            swap = swap2;
        }
        return min(keep, swap);
    }
};
      

class Solution {
    public int minSwap(int[] A, int[] B) {
        int n = A.length;
        int keep = 0, swap = 1;
        for (int i = 1; i < n; i++) {
            int keep2 = Integer.MAX_VALUE, swap2 = Integer.MAX_VALUE;
            if (A[i] > A[i-1] && B[i] > B[i-1]) {
                keep2 = Math.min(keep2, keep);
                swap2 = Math.min(swap2, swap + 1);
            }
            if (A[i] > B[i-1] && B[i] > A[i-1]) {
                keep2 = Math.min(keep2, swap);
                swap2 = Math.min(swap2, keep + 1);
            }
            keep = keep2;
            swap = swap2;
        }
        return Math.min(keep, swap);
    }
}
      

var minSwap = function(A, B) {
    let n = A.length;
    let keep = 0, swap = 1;
    for (let i = 1; i < n; i++) {
        let keep2 = Infinity, swap2 = Infinity;
        if (A[i] > A[i-1] && B[i] > B[i-1]) {
            keep2 = Math.min(keep2, keep);
            swap2 = Math.min(swap2, swap + 1);
        }
        if (A[i] > B[i-1] && B[i] > A[i-1]) {
            keep2 = Math.min(keep2, swap);
            swap2 = Math.min(swap2, keep + 1);
        }
        keep = keep2;
        swap = swap2;
    }
    return Math.min(keep, swap);
};