Minimum Swaps To Make Sequences Increasing - Leetcode Solution

Problem Statement:

You are given two integer arrays of equal length, A and B.

In one operation, you can choose two indices i and j, where 0 <= i <= j < A.length and swap A[i] with A[j].

If A and B are both strictly increasing, then the arrays are considered to be increasing.

Return the minimum number of operations needed to make A and B increasing. The answer will be guaranteed to be less than or equal to 10^9.

Example 1:

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.

Solution:

The problem is to make A and B increasing by swapping the elements between A and B having the same index.

We can solve this problem using dynamic programming where dp[i][0] is the minimum number of swaps required to make A and B increasing by i elements and we don't swap the ith element and dp[i][1] is the minimum number of swaps required to make A and B increasing by i elements and we swap the ith element.

To compute dp[i][0], there are two possibilities:

1. We do not swap ith element
2. We swap ith element

If we do not swap the ith element, then we need to ensure that A[i] > A[i-1] and B[i] > B[i-1] since we are not changing the ith element.

If we swap the ith element, then we need to ensure that A[i] > B[i-1] and B[i] > A[i-1] since we are swapping the ith element.

Similarly, to compute dp[i][1], there are two possibilities:

1. We do not swap ith element
2. We swap ith element

If we do not swap the ith element, then we need to ensure that A[i] > B[i-1] and B[i] > A[i-1] since we are not changing the ith element.

If we swap the ith element, then we need to ensure that A[i] > A[i-1] and B[i] > B[i-1] since we are swapping the ith element.

To find the minimum number of swaps required to make A and B increasing, we can take the minimum of dp[n-1][0] and dp[n-1][1], where n is the length of A and B.

The time complexity of this solution is O(n) and the space complexity is O(n).

Here is the code in Python:

def minSwap(A, B):

n = len(A)

# Initialize dp array
dp = [[float('inf')]*2 for i in range(n)]

# Initialize base cases
dp[0][0] = 0  # We do not swap first element
dp[0][1] = 1  # We swap first element

# Loop through all elements
for i in range(1, n):
    
    # If we do not swap ith element
    if A[i] > A[i-1] and B[i] > B[i-1]:
        dp[i][0] = dp[i-1][0]  # We do not need to swap
    
    # If we swap ith element
    if A[i] > B[i-1] and B[i] > A[i-1]:
        dp[i][1] = dp[i-1][0] + 1  # We need to swap
    
    # If we do not swap ith element
    if A[i] > B[i-1] and B[i] > A[i-1]:
        dp[i][0] = min(dp[i][0], dp[i-1][1])  # We need to swap
    
    # If we swap ith element
    if A[i] > A[i-1] and B[i] > B[i-1]:
        dp[i][1] = min(dp[i][1], dp[i-1][1] + 1)  # We do not need to swap
    
# Return the minimum number of swaps required
return min(dp[n-1][0], dp[n-1][1])

1