Watch 10 video solutions for Make Array Strictly Increasing, a hard level problem involving Array, Binary Search, Dynamic Programming. This walkthrough by codestorywithMIK has 8,661 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |