Make Array Strictly Increasing LeetCode solution in Python

1
class Solution:
2
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
3
        n1, n2, dp = len(arr1), len(arr2), {}
4
        arr2.sort()
5

6
        def solve(i, j, prev):
7

8
            if i == n1:
9
                return 0
10

11
            if (i, j, prev) in dp:
12
                return dp[(i, j, prev)]
13

14
            k = bisect.bisect_right(arr2[j:], prev) + j
15

16
            ans = float("inf") if k == n2 else solve(i + 1, k + 1, arr2[k]) + 1
17

18
            if arr1[i] > prev:
19
                ans = min(ans, solve(i + 1, j, arr1[i]))
20

21
            dp[(i, j, prev)] = ans
22

23
            return ans
24

25
        ans = solve(0, 0, -float("inf"))
26

27
        return ans if ans != float("inf") else -1