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.
1using System;
2
3public class Solution {
4 public int MakeArrayIncreasing(int[] arr1, int[] arr2) {
5 Array.Sort(arr2);
6 int n = arr1.Length;
7 int[] dp = new int[n + 1];
8 Array.Fill(dp, int.MaxValue);
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 = Array.BinarySearch(arr2, arr1[j - 1] + 1);
16 if (pos < 0) pos = ~pos;
17 if (pos < arr2.Length) {
18 dp[i] = Math.Min(dp[i], dp[j] + 1);
19 }
20 }
21 }
22 return dp[n] == int.MaxValue ? -1 : dp[n];
23 }
24
25 public static void Main(string[] args) {
26 var 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 Console.WriteLine(result);
31 }
32}The C# solution uses the Array.Sort and Array.BinarySearch methods for handling the search and sorting operations. Similar to the other languages, it uses dynamic programming to find the optimal sequence transformations.