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.
1import java.util.*;
2
3public class Solution {
4 public int makeArrayIncreasing(int[] arr1, int[] arr2) {
5 Arrays.sort(arr2);
6 int n = arr1.length;
7 int[] dp = new int[n + 1];
8 Arrays.fill(dp, Integer.MAX_VALUE);
9 dp[0] = 0;
10 for (int i = 1; i <= n; i++) {
11 for (int j = i - 1; j >= 0; j--) {
12 if (j == 0 || arr1[j - 1] < arr1[i - 1]) {
13 dp[i] = Math.min(dp[i], dp[j]);
14 }
15 int pos = Arrays.binarySearch(arr2, arr1[j - 1] + 1);
16 if (pos < 0) pos = -pos - 1;
17 if (pos < arr2.length) {
18 dp[i] = Math.min(dp[i], dp[j] + 1);
19 }
20 }
21 }
22 return dp[n] == Integer.MAX_VALUE ? -1 : dp[n];
23 }
24
25 public static void main(String[] args) {
26 Solution sol = new Solution();
27 int[] arr1 = {1, 5, 3, 6, 7};
28 int[] arr2 = {1, 3, 2, 4};
29 int result = sol.makeArrayIncreasing(arr1, arr2);
30 System.out.println(result);
31 }
32}In the Java solution, Arrays.sort is used to sort arr2 and Arrays.binarySearch for binary search. The dynamic programming approach mimics the state transitions found in the C++ solution, leveraging indexed elements optimally.