Make Array Strictly Increasing
HardUpdated: Aug 2, 2025
Practice on:
Make Array Strictly Increasing Problem
Problem
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.
Examples
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.
Solution
Method 1 – Dynamic Programming with Binary Search
Intuition
We use DP to track the minimum operations needed to make the array strictly increasing up to each index, considering both keeping the current value and replacing it with a value from arr2. Binary search helps efficiently find the next possible replacement.
Approach
- Sort arr2 and remove duplicates for efficient searching.
- Use a DP map: key is the previous value, value is the minimum operations to reach that state.
- For each index in arr1:
- For each possible previous value in DP:
- If arr1[i] > prev, keep arr1[i].
- Use binary search to find the smallest value in arr2 > prev, and replace arr1[i].
- Update DP for the next index.
- For each possible previous value in DP:
- The answer is the minimum operations in the last DP map.
Code
C++
class Solution {
public:
int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
set<int> s(arr2.begin(), arr2.end());
vector<int> b(s.begin(), s.end());
map<int, int> dp;
dp[-1] = 0;
for (int a : arr1) {
map<int, int> ndp;
for (auto& [prev, ops] : dp) {
if (a > prev) ndp[a] = ndp.count(a) ? min(ndp[a], ops) : ops;
auto it = upper_bound(b.begin(), b.end(), prev);
if (it != b.end()) ndp[*it] = ndp.count(*it) ? min(ndp[*it], ops+1) : ops+1;
}
dp = ndp;
}
if (dp.empty()) return -1;
int ans = INT_MAX;
for (auto& [k, v] : dp) ans = min(ans, v);
return ans;
}
};
Go
func makeArrayIncreasing(arr1, arr2 []int) int {
s := map[int]struct{}{}
for _, x := range arr2 {
s[x] = struct{}{}
}
b := []int{}
for x := range s {
b = append(b, x)
}
sort.Ints(b)
dp := map[int]int{-1: 0}
for _, a := range arr1 {
ndp := map[int]int{}
for prev, ops := range dp {
if a > prev {
if v, ok := ndp[a]; !ok || ops < v {
ndp[a] = ops
}
}
idx := sort.SearchInts(b, prev+1)
if idx < len(b) {
if v, ok := ndp[b[idx]]; !ok || ops+1 < v {
ndp[b[idx]] = ops+1
}
}
}
dp = ndp
}
if len(dp) == 0 {
return -1
}
ans := 1<<30
for _, v := range dp {
if v < ans {
ans = v
}
}
return ans
}
Java
class Solution {
public int makeArrayIncreasing(int[] arr1, int[] arr2) {
TreeSet<Integer> set = new TreeSet<>();
for (int x : arr2) set.add(x);
int[] b = set.stream().mapToInt(i->i).toArray();
Map<Integer, Integer> dp = new HashMap<>();
dp.put(-1, 0);
for (int a : arr1) {
Map<Integer, Integer> ndp = new HashMap<>();
for (int prev : dp.keySet()) {
int ops = dp.get(prev);
if (a > prev) ndp.put(a, Math.min(ndp.getOrDefault(a, Integer.MAX_VALUE), ops));
int idx = Arrays.binarySearch(b, prev+1);
if (idx < 0) idx = -idx-1;
if (idx < b.length) ndp.put(b[idx], Math.min(ndp.getOrDefault(b[idx], Integer.MAX_VALUE), ops+1));
}
dp = ndp;
}
if (dp.isEmpty()) return -1;
int ans = Integer.MAX_VALUE;
for (int v : dp.values()) ans = Math.min(ans, v);
return ans;
}
}
Kotlin
class Solution {
fun makeArrayIncreasing(arr1: IntArray, arr2: IntArray): Int {
val set = arr2.toSet()
val b = set.sorted()
var dp = mutableMapOf(-1 to 0)
for (a in arr1) {
val ndp = mutableMapOf<Int, Int>()
for ((prev, ops) in dp) {
if (a > prev) ndp[a] = minOf(ndp.getOrDefault(a, Int.MAX_VALUE), ops)
val idx = b.binarySearch(prev+1).let { if (it < 0) -it-1 else it }
if (idx < b.size) ndp[b[idx]] = minOf(ndp.getOrDefault(b[idx], Int.MAX_VALUE), ops+1)
}
dp = ndp
}
if (dp.isEmpty()) return -1
return dp.values.minOrNull() ?: -1
}
}
Python
class Solution:
def makeArrayIncreasing(self, arr1: list[int], arr2: list[int]) -> int:
b = sorted(set(arr2))
dp = {-1: 0}
for a in arr1:
ndp = {}
for prev, ops in dp.items():
if a > prev:
ndp[a] = min(ndp.get(a, float('inf')), ops)
import bisect
idx = bisect.bisect_right(b, prev)
if idx < len(b):
ndp[b[idx]] = min(ndp.get(b[idx], float('inf')), ops+1)
dp = ndp
if not dp:
return -1
return min(dp.values())
Rust
impl Solution {
pub fn make_array_increasing(arr1: Vec<i32>, arr2: Vec<i32>) -> i32 {
use std::collections::HashMap;
let mut b = arr2.clone();
b.sort();
b.dedup();
let mut dp = HashMap::new();
dp.insert(-1, 0);
for &a in &arr1 {
let mut ndp = HashMap::new();
for (&prev, &ops) in &dp {
if a > prev {
ndp.insert(a, ndp.get(&a).map_or(ops, |&v| v.min(ops)));
}
if let Ok(idx) = b.binary_search(&(prev+1)) {
if idx < b.len() {
let v = ndp.get(&b[idx]).map_or(ops+1, |&x| x.min(ops+1));
ndp.insert(b[idx], v);
}
} else if let Err(idx) = b.binary_search(&(prev+1)) {
if idx < b.len() {
let v = ndp.get(&b[idx]).map_or(ops+1, |&x| x.min(ops+1));
ndp.insert(b[idx], v);
}
}
}
dp = ndp;
}
if dp.is_empty() { return -1; }
*dp.values().min().unwrap()
}
}
TypeScript
class Solution {
makeArrayIncreasing(arr1: number[], arr2: number[]): number {
const b = Array.from(new Set(arr2)).sort((a, b) => a - b)
let dp = new Map<number, number>([[-1, 0]])
for (const a of arr1) {
const ndp = new Map<number, number>()
for (const [prev, ops] of dp.entries()) {
if (a > prev) ndp.set(a, Math.min(ndp.get(a) ?? Infinity, ops))
const idx = b.findIndex(x => x > prev)
if (idx !== -1) ndp.set(b[idx], Math.min(ndp.get(b[idx]) ?? Infinity, ops+1))
}
dp = ndp
}
if (dp.size === 0) return -1
return Math.min(...dp.values())
}
}
Complexity
- ⏰ Time complexity:
O(nm log m)— n is length of arr1, m is length of arr2. - 🧺 Space complexity:
O(nm)— For DP maps.