BinarySearch 0645 Minimum Number of Operations to Make Lists Increasing

Problem statement

https://binarysearch.com/problems/Minimum-Number-of-Operations-to-Make-Lists-Increasing/

Solution

Equal to Leetcode 0801 Minimum Swaps To Make Sequences Increasing.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(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])