Given two integer arrays arr1 and arr2, return the minimum number of operations (possibly zero) needed to make arr1 strictly increasing.
In one operation, you can choose two indices 0 <= i < arr1.length and 0 <= j < arr2.length and do the assignment arr1[i] = arr2[j].
If there is no way to make arr1 strictly increasing, return -1.
Example 1:
Input: arr1 = [1,5,3,6,7], arr2 = [1,3,2,4] Output: 1 Explanation: Replace5with2, thenarr1 = [1, 2, 3, 6, 7].
Example 2:
Input: arr1 = [1,5,3,6,7], arr2 = [4,3,1] Output: 2 Explanation: Replace5with3and then replace3with4.arr1 = [1, 3, 4, 6, 7].
Example 3:
Input: arr1 = [1,5,3,6,7], arr2 = [1,6,3,3]
Output: -1
Explanation: You can't make arr1 strictly increasing.
Constraints:
1 <= arr1.length, arr2.length <= 20000 <= arr1[i], arr2[i] <= 10^9
Problem Overview: You are given two arrays arr1 and arr2. You may replace elements in arr1 with elements from arr2. The goal is to make arr1 strictly increasing with the minimum number of replacements. If it cannot be done, return -1.
The challenge is choosing which positions to replace and which values from arr2 to use so the sequence remains strictly increasing. Since multiple choices exist at every index, a greedy strategy alone fails. You need a state-based method that tracks the best increasing sequences built so far.
Approach 1: Brute Force Replacement Search (Exponential Time, O(2^n) time, O(n) space)
A naive approach tries every possible decision at each index: keep the current value from arr1 or replace it with any valid value from arr2. You recursively build sequences and check whether they remain strictly increasing. This quickly becomes infeasible because each position may branch into multiple replacement choices. Even with pruning, the state space grows exponentially. This approach mainly helps understand the decision structure before introducing dynamic programming.
Approach 2: Dynamic Programming with Binary Search (O(n log m) time, O(n) space)
The optimal strategy treats the problem as a state transition. Track the smallest possible ending value of a strictly increasing sequence after processing index i with k replacements. Sort arr2 first so you can efficiently find the next valid replacement using binary search. For every element in arr1, you have two transitions: keep the value if it is greater than the previous element, or replace it with the smallest value in arr2 that is greater than the previous value.
A hash map or DP map stores states as {last_value -> min_operations}. When processing the next element, generate new states for both decisions. Using sorted arr2 allows a fast lookup of the smallest valid replacement via upper_bound. Prune states that are dominated by better ones to keep the state space small. This combines dynamic programming for optimal substructure with binary search to efficiently choose replacement values.
Sorting arr2 once enables fast lookups and ensures replacements maintain increasing order. The DP state size stays manageable because only the smallest operation count for each possible ending value is preserved. This results in an efficient solution with O(n log m) time where m is the size of arr2.
Recommended for interviews: The dynamic programming with binary search approach is what interviewers expect. The brute force reasoning shows you understand the decision tree, but the optimized DP demonstrates mastery of array state transitions, pruning techniques, and efficient search.
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.
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.
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.
We define f[i] as the minimum number of operations to convert arr1[0,..,i] into a strictly increasing array, and arr1[i] is not replaced. Therefore, we set two sentinels -infty and infty at the beginning and end of arr1. The last number is definitely not replaced, so f[n-1] is the answer. We initialize f[0]=0, and the rest f[i]=infty.
Next, we sort the array arr2 and remove duplicates for easy binary search.
For i=1,..,n-1, we consider whether arr1[i-1] is replaced. If arr1[i-1] \lt arr1[i], then f[i] can be transferred from f[i-1], that is, f[i] = f[i-1]. Then, we consider the case where arr[i-1] is replaced. Obviously, arr[i-1] should be replaced with a number as large as possible and less than arr[i]. We perform a binary search in the array arr2 and find the first index j that is greater than or equal to arr[i]. Then we enumerate the number of replacements in the range k \in [1, min(i-1, j)]. If arr[i-k-1] \lt arr2[j-k], then f[i] can be transferred from f[i-k-1], that is, f[i] = min(f[i], f[i-k-1] + k).
Finally, if f[n-1] geq infty, it means that it cannot be converted into a strictly increasing array, return -1, otherwise return f[n-1].
The time complexity is (n times (log m + min(m, n))), and the space complexity is O(n). Here, n is the length of arr1.
| Approach | Complexity |
|---|---|
| Dynamic Programming with Binary Search | Time Complexity: O(n * m * log m), where n is the length of arr1 and m is the length of arr2. |
| Dynamic Programming | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Replacement Search | O(2^n) | O(n) | Conceptual understanding of the decision tree and replacement choices |
| Dynamic Programming with Binary Search | O(n log m) | O(n) | General case and optimal solution for interviews and competitive programming |
Make Array Strictly Increasing | Recur + Memo | Time Complexity | GOOGLE | Leetcode-1187 | Live Code • codestorywithMIK • 8,661 views views
Watch 9 more video solutions →Practice Make Array Strictly Increasing with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor