Sponsored
Sponsored
This approach uses dynamic programming with binary search to efficiently determine the minimum number of transformations required to make arr1 strictly increasing. The idea is to maintain a state dp[i] representing the minimum operations required to make arr1 up to index i strictly increasing. For each element in arr1, there are two choices: keep the current element or replace it with an element from arr2. Use binary search to quickly find a suitable replacement from the sorted array arr2. Transition between states takes the minimum of both choices.
Time Complexity: O(n * m * log m), where n is the length of arr1 and m is the length of arr2.
Space Complexity: O(n) for the dp array.
1from bisect import bisect_right
2
3class Solution:
4 def makeArrayIncreasing(self, arr1, arr2):
5 arr2.sort()
6 n = len(arr1)
7 dp = [float('inf')] * (n + 1)
8 dp[0] = 0
9 for i in range(1, n + 1):
10 for j in range(i - 1, -1, -1):
11 if j == 0 or arr1[j - 1] < arr1[i - 1]:
12 dp[i] = min(dp[i], dp[j])
13 pos = bisect_right(arr2, arr1[j - 1])
14 if pos < len(arr2):
15 dp[i] = min(dp[i], dp[j] + 1)
16 return -1 if dp[n] == float('inf') else dp[n]
17
18# Example usage
19sol = Solution()
20arr1 = [1, 5, 3, 6, 7]
21arr2 = [1, 3, 2, 4]
22result = sol.makeArrayIncreasing(arr1, arr2)
23print(result)The Python solution employs the bisect module for efficient searching and maintains a dynamic programming array to store minimal operations required at every step to keep arr1 strictly increasing.