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 <vector>
2#include <algorithm>
3#include <climits>
4
5using namespace std;
6
7class Solution {
8public:
9 int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
10 sort(arr2.begin(), arr2.end());
11 int n = arr1.size(), m = arr2.size();
12 vector<int> dp(n + 1, INT_MAX);
13 dp[0] = 0;
14 for (int i = 1; i <= n; ++i) {
15 for (int j = 0; j < i; ++j) {
16 if (arr1[j - 1] < arr1[i - 1]) {
17 dp[i] = min(dp[i], dp[j]);
18 }
19 int pos = lower_bound(arr2.begin(), arr2.end(), arr1[j - 1] + 1) - arr2.begin();
20 if (pos < m) {
21 dp[i] = min(dp[i], dp[j] + 1);
22 }
23 }
24 }
25 return dp[n] == INT_MAX ? -1 : dp[n];
26 }
27};
28
29int main() {
30 Solution sol;
31 vector<int> arr1 = {1, 5, 3, 6, 7};
32 vector<int> arr2 = {1, 3, 2, 4};
33 int result = sol.makeArrayIncreasing(arr1, arr2);
34 cout << result << endl;
35 return 0;
36}This C++ solution leverages STL functions such as sort and lower_bound for binary search. Dynamic programming is used to keep track of the minimum number of operations required to ensure arr1 is strictly increasing.