Problem statement

https://leetcode.com/problems/minimum-swaps-to-make-sequences-increasing/

Solution

Let dp1[k] be answer for first $k$ indexes, if we do not swap last pair and dp2[k] the same if we swap last pair. Then:

  1. if A[i] < A[i+1] and B[i] < B[i+1] it means, that we have dp[i] option for dp[i+1] anddp2[i] + 1 option for dp2[i+1] we need to make one more swap here.
  2. if B[i] < A[i+1] and A[i] < B[i+1] (this is not exclusive option, both can happen!), then we have dp2[i] option for dp1[i+1] anddp1[i] + 1 option for dp2[i+1], here we need to add one more swap here.

Complexity

Time complexity is O(n), space as well. Space can be reduced to O(1).

Code

class Solution:
    def minSwap(self, A, B):
        n = len(A)
        dp1 = [0] + [float("inf")]*(n-1)
        dp2 = [1] + [float("inf")]*(n-1)

        for i in range(n-1):
            if A[i] < A[i+1] and B[i] < B[i+1]: 
                dp1[i+1] = min(dp1[i+1], dp1[i])
                dp2[i+1] = min(dp2[i+1], dp2[i] + 1)
            if B[i] < A[i+1] and A[i] < B[i+1]:
                dp1[i+1] = min(dp1[i+1], dp2[i])
                dp2[i+1] = min(dp2[i+1], dp1[i] + 1)
                
        return min(dp1[-1], dp2[-1])