Problem statement

https://leetcode.com/problems/make-array-strictly-increasing/

Solution 1

The idea is to use dp with state dp(i, last) where i is the index in arr1 and last is the last value in built sequence. Here is implementation without lru_cache, when we go line by line. When we increase i-1 -> i, we can have two options:

  1. Increase value of i-th element in arr1, such that it becomes bigger than previous. We must take the smallest element biggest than last, and specifically for this we created f dictionary.
  2. Keep value of i-th element unchanged: we can do it only in the case when arr1[i] > last.

Why we can not use lru_cache here? Because to go from level i-1 to level i, we can create arrows in bipartitie graph, but we can not easily evaluate inverse arrows.

Complexity

Time complexity is O(n*m), because we can have upto m+1 values for last on each state - m of them from arr2 and one if we keep it unchanged. Space complexity is O(m).

Code

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

Solution 2

Actually, there is a way to do it with lru_cache as well if we put state dp(i, prev), where prev is previous element in arr1. So, the idea is to go in opposite direction.

Complexity

It is still O(nm) for time, but O(nm) for space as well.

Code

class Solution:
    def makeArrayIncreasing(self, arr1, arr2):
        arr2 = sorted(set(arr2))
        m, n, f = len(arr2), len(arr1), {}
        
        for num in arr1 + arr2 + [-1]:
            q = bisect.bisect(arr2, num)
            if q < len(arr2): f[num] = arr2[q]
        
        @lru_cache(None)
        def dp(i, prev):
            if i >= n: return 0
            ans = float("inf")
            if prev in f: ans = min(ans, 1 + dp(i + 1, f[prev]))
            if arr1[i] > prev: ans = min(ans, dp(i + 1, arr1[i]))
            return ans
            
        ans = dp(0, -1)
        return ans if ans != float("inf") else -1