Skip to main content
Talentd

Make Array Strictly Increasing - Solution & Explanation

HardArrayBinary SearchDynamic ProgrammingSorting19 min read
Practice this problem

Problem Statement

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: Replace 5 with 2, then arr1 = [1, 2, 3, 6, 7].

Example 2:

Input: arr1 = [1,5,3,6,7], arr2 = [4,3,1]
Output: 2
Explanation: Replace 5 with 3 and then replace 3 with 4. 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 <= 2000
  • 0 <= arr1[i], arr2[i] <= 10^9

 

Approach Overview

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 1: Dynamic Programming with Binary 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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Dynamic Programming

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.

Code

PythonJavaC++GoTypeScriptC#

Python

Java

C++

Go

TypeScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(n) for the dp array.

Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Replacement SearchO(2^n)O(n)Conceptual understanding of the decision tree and replacement choices
Dynamic Programming with Binary SearchO(n log m)O(n)General case and optimal solution for interviews and competitive programming

Video Solution

Make Array Strictly Increasing | Recur + Memo | Time Complexity | GOOGLE | Leetcode-1187 | Live Code • codestorywithMIK • 9,610 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Make Array Strictly Increasing easy or hard?
Make Array Strictly Increasing is classified as a Hard problem because it combines dynamic programming, binary search, and careful state pruning. The difficulty comes from managing multiple possible sequence endings while minimizing operations without letting the state space explode.
Make Array Strictly Increasing Python/Java solution
Python and Java implementations usually sort arr2, then maintain a dictionary or map representing DP states. Each iteration processes the next element of arr1 and updates states for both keeping and replacing values. Binary search functions such as bisect in Python or Collections.binarySearch in Java help locate the next valid replacement efficiently.
How to solve Make Array Strictly Increasing in O(n log m)?
Sort arr2 and remove duplicates if necessary. Use dynamic programming where each state tracks the minimum operations needed for sequences ending at a specific value. For each element in arr1, either keep it if it maintains increasing order or replace it using the smallest greater element from arr2 found via binary search. Update states and prune dominated ones to keep the DP efficient.
What is the best approach for Make Array Strictly Increasing?
Dynamic programming with binary search is the most efficient approach. Sort arr2 and maintain DP states representing the minimum operations required for sequences ending with a specific value. Binary search finds the smallest replacement value greater than the previous element, keeping the sequence strictly increasing. This reduces the complexity to O(n log m).
Is Make Array Strictly Increasing asked at Google/Amazon/Meta?
Problems involving dynamic programming with binary search and sequence transformations commonly appear in interviews at companies like Google, Amazon, and Meta. Variants of this problem test state transitions, pruning strategies, and efficient searching in sorted arrays.
What data structure is used in Make Array Strictly Increasing?
The solution typically uses arrays, sorted lists, hash maps for DP state tracking, and binary search on arr2. Sorting enables fast lookups of the next valid replacement value, while the DP map keeps the best operation count for each possible ending value.
What is the time complexity of Make Array Strictly Increasing?
The optimal solution runs in O(n log m) time, where n is the length of arr1 and m is the length of arr2. Sorting arr2 takes O(m log m), and each element in arr1 performs binary search on arr2. Space complexity is typically O(n) for storing dynamic programming states.

Ready to solve this problem?

Practice Make Array Strictly Increasing with our built-in code editor and test cases.

Practice on FleetCode
Previous

Make Array Non-decreasing or Non-increasing