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.
1const makeArrayIncreasing = (arr1, arr2) => {
2 arr2.sort((a, b) => a - b);
3 const n = arr1.length;
4 const dp = new Array(n + 1).fill(Infinity);
5 dp[0] = 0;
6 for (let i = 1; i <= n; i++) {
7 for (let j = i - 1; j >= 0; j--) {
8 if (j === 0 || arr1[j - 1] < arr1[i - 1]) {
9 dp[i] = Math.min(dp[i], dp[j]);
10 }
11 let pos = bisectRight(arr2, arr1[j - 1]);
12 if (pos < arr2.length) {
13 dp[i] = Math.min(dp[i], dp[j] + 1);
14 }
15 }
16 }
17 return dp[n] === Infinity ? -1 : dp[n];
18};
19
20const bisectRight = (arr, x) => {
21 let lo = 0, hi = arr.length;
22 while (lo < hi) {
23 const mid = Math.floor((lo + hi) / 2);
24 if (arr[mid] <= x) {
25 lo = mid + 1;
26 } else {
27 hi = mid;
28 }
29 }
30 return lo;
31};
32
33// Example usage
34const arr1 = [1, 5, 3, 6, 7];
35const arr2 = [1, 3, 2, 4];
36console.log(makeArrayIncreasing(arr1, arr2));The JavaScript solution sorts arr2 and uses a custom bisectRight function to perform binary search operations. Dynamic programming is applied to keep track of minimal operations necessary for achieving a strictly increasing order for arr1.