🚀

End of Year Sale: Use Coupon Code END2025 to Get Extra 25% Off.

11DAYS
:
18HOURS
:
43MINUTES
:
52SECONDS

Leetcode Problem 1187. Make Array Strictly Increasing

1187. Make Array Strictly Increasing

Leetcode Solutions

Top-down Dynamic Programming Approach

  1. Sort arr2.
  2. Initialize a hash map dp as memory.
  3. Define a function dfs(i, prev) to find the minimum number of operations to make arr1[i:] sorted when arr1[i - 1] = prev.
    • If (i, prev) exists in dp, return dp[(i, prev)].
    • If arr1[i] > prev, set cost to dfs(i+1, arr1[i]).
    • Use binary search to find the index idx of the smallest value in arr2 greater than prev. If idx < len(arr2), set cost to min(cost, 1 + dfs(i+1, arr2[idx])).
    • Update dp[(i, prev)] with cost.
    • Return cost.
  4. Call dfs(0, -1) and return its value if it's not float('inf'), otherwise return -1.
UML Thumbnail

Bottom-up Dynamic Programming Approach

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...