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.
1#include <stdio.h>
2#include <stdlib.h>
3#include <limits.h>
4
5int compare(const void *a, const void *b) {
6 return (*(int *)a - *(int *)b);
7}
8
9int binarySearch(int* arr, int size, int x) {
10 int left = 0, right = size - 1;
11 while (left <= right) {
12 int mid = left + (right - left) / 2;
13 if (arr[mid] <= x)
14 left = mid + 1;
15 else
16 right = mid - 1;
17 }
18 return left < size ? left : -1;
19}
20
21int makeArrayIncreasing(int* arr1, int arr1Size, int* arr2, int arr2Size) {
22 qsort(arr2, arr2Size, sizeof(int), compare);
23 int* dp = malloc((arr1Size + 1) * sizeof(int));
24 dp[0] = 0;
25 for (int i = 1; i <= arr1Size; ++i) {
26 dp[i] = INT_MAX;
27 if (arr1[i - 1] > arr1[i - 2]) {
28 dp[i] = dp[i - 1];
29 }
30 int pos = binarySearch(arr2, arr2Size, arr1[i - 2]);
31 if (pos != -1) {
32 dp[i] = fmin(dp[i], dp[i - 1] + 1);
33 }
34 }
35 int result = dp[arr1Size];
36 free(dp);
37 return result == INT_MAX ? -1 : result;
38}
39
40int main() {
41 int arr1[] = {1, 5, 3, 6, 7};
42 int arr2[] = {1, 3, 2, 4};
43 int result = makeArrayIncreasing(arr1, sizeof(arr1) / sizeof(arr1[0]), arr2, sizeof(arr2) / sizeof(arr2[0]));
44 printf("%d\n", result);
45 return 0;
46}The C solution sorts arr2 first to enable efficient binary search. Then it iterates through arr1 while maintaining the dynamic programming state dp, which counts the minimal number of operations needed to ensure arr1 is strictly increasing up to each index. A binary search is performed to find potential replacements from arr2.