Problem can be found in here!
Solution: Dynamic Programming
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
Time Complexity: , Space Complexity: , where m is the length of arr1 array and n is the length of arr2 array.