Leetcode/Dynamic Programming/1187-MakeArrayStrictlyIncreasing/solution.py at main · yuchia0221/Leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from functools import cache
from typing import List
from bisect import bisect_right


def makeArrayIncreasing(arr1: List[int], arr2: List[int]) -> int:
    @cache
    def get_minimum_operations(index: int, previous_value: int) -> int:
        if index == len(arr1):
            return 0

        current_cost = float("inf")
        if arr1[index] > previous_value:
            current_cost = get_minimum_operations(index+1, arr1[index])

        new_index = bisect_right(arr2, previous_value)
        if new_index < len(arr2):
            current_cost = min(current_cost, 1 + get_minimum_operations(index+1, arr2[new_index]))

        return current_cost

    arr2.sort()
    minimum_operations = get_minimum_operations(0, -1)
    return minimum_operations if minimum_operations != float("inf") else -1