BinarySearch 0888 Update List to Make It Strictly Increasing

Problem statement

https://binarysearch.com/problems/Update-List-to-Make-It-Strictly-Increasing/

Solution

Equal to Leetcode 1187. Make Array Strictly Increasing.

Complexity

It is O(mn) for time and O(m) for space.

Code

class Solution:
    def solve(self, arr1, arr2):
        arr2 = sorted(list(set(arr2)))
        f, n, dp = {}, len(arr1), {-1: 0}
        
        for num in arr1 + arr2 + [-1]:
            q = bisect.bisect(arr2, num)
            if q < len(arr2): f[num] = arr2[q]

        for i in range(n):
            dp2 = defaultdict(lambda: float('inf'))
            for last, a in dp.items():
                if last in f: dp2[f[last]] = min(dp2[f[last]], a + 1)
                if arr1[i] > last: dp2[arr1[i]] = min(dp2[arr1[i]], a)
            dp = dp2

        return -1 if not dp else min(dp.values())