Minimum Swaps To Make Sequences Increasing LeetCode solution in Python

1
# Runtime: 1198 ms (Top 36.1%) | Memory: 149.20 MB (Top 27.6%)
2

3

4
class Solution:
5
    def minSwap(self, nums1: List[int], nums2: List[int]) -> int:
6
        dp = [[-1] * 2 for i in range(len(nums1))]
7

8
        def solve(prev1, prev2, i, swaped):
9
            if i >= len(nums1):
10
                return 0
11
            if dp[i][swaped] != -1:
12
                return dp[i][swaped]
13

14
            ans = 2**31
15

16
            # No Swap
17
            if nums1[i] > prev1 and nums2[i] > prev2:
18
                ans = solve(nums1[i], nums2[i], i + 1, 0)
19

20
            # Swap
21
            if nums1[i] > prev2 and nums2[i] > prev1:
22
                ans = min(ans, 1 + solve(nums2[i], nums1[i], i + 1, 1))
23

24
            dp[i][swaped] = ans
25
            return ans
26

27
        return solve(-1, -1, 0, 0)