Make Array Strictly Increasing — Problem & Solution
Make Array Strictly Increasing solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Make Array Strictly Increasing is a hard coding problem on arrays, dynamic programming and sorting, asked in Amazon, Google and Meta interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming, Sorting, Binary Search
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
In one operation you may replace any element of arr1 with any element of arr2 — elements of arr2 may be reused.
Return the minimum number of operations that makes arr1 strictly increasing, or -1 if that is impossible.
Example 1
Input: arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
Output: 1
Explanation: Replace the 5 with 2.
Example 2
Input: arr1 = [1,5,3,6,7], arr2 = [4,3,1]
Output: 2
Explanation: Replace the 5 with 3 and the 3 with 4.
Example 3
Input: arr1 = [1,5,3,6,7], arr2 = [1,6,3,3]
Output: -1
Constraints
1 <= arr1.length, arr2.length <= 20000 <= arr1[i], arr2[i] <= 10^9
Hints for Make Array Strictly Increasing
Hint 1
The only thing the future depends on is the value the prefix currently ends on, and how many operations got you there.
Hint 2
So keep a map from that ending value to the fewest operations.
Hint 3
At each step either keep
arr1[i](if it is larger than the previous value) or replace it with the smallest element ofarr2that is larger.
How to solve Make Array Strictly Increasing
A DP over "what value does the prefix end on". Carry a map from ending value to the minimum operations used. For each position, extend every state two ways: keep arr1[i] when it exceeds the previous value, or replace it with the smallest element of the sorted arr2 that exceeds the previous value.
Approach
- Sort
arr2once. - Start from the single state
{-1: 0}— nothing placed yet, using a sentinel below every value. - For each element of
arr1, build the next map from both transitions, keeping the smaller operation count per ending value. - The answer is the smallest value in the final map, or
-1if it is empty.
Why it works
Only the smallest valid replacement ever needs considering: a larger one costs the same operation but leaves less room for what follows, so it is dominated. That collapses the branching from |arr2| to 1 per state, and the state count stays small because the reachable ending values are always either arr1[i] or an element of arr2.
Complexity
- Time —
O(n · m log m) - Space —
O(m)
Pitfalls
- "Strictly" increasing — equal neighbours are not allowed, so the search is for a value strictly greater.
- Elements of
arr2may be reused any number of times. - An empty state map means the array cannot be fixed, which is the
-1case.
Reference solution
Python
from bisect import bisect_right
from typing import List
def makeArrayIncreasing(arr1: List[int], arr2: List[int]) -> int:
pool = sorted(arr2)
dp = {-1: 0}
for v in arr1:
nxt = {}
for prev, ops in dp.items():
if v > prev:
if v not in nxt or ops < nxt[v]:
nxt[v] = ops
j = bisect_right(pool, prev)
if j < len(pool):
cand = pool[j]
if cand not in nxt or ops + 1 < nxt[cand]:
nxt[cand] = ops + 1
dp = nxt
return min(dp.values()) if dp else -1Java
public static int makeArrayIncreasing(int[] arr1, int[] arr2) {
int[] pool = arr2.clone();
Arrays.sort(pool);
Map<Integer, Integer> dp = new HashMap<>();
dp.put(-1, 0);
for (int v : arr1) {
Map<Integer, Integer> next = new HashMap<>();
for (Map.Entry<Integer, Integer> e : dp.entrySet()) {
int prev = e.getKey(), ops = e.getValue();
if (v > prev) {
Integer cur = next.get(v);
if (cur == null || ops < cur) next.put(v, ops);
}
int lo = 0, hi = pool.length;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (pool[mid] > prev) hi = mid;
else lo = mid + 1;
}
if (lo < pool.length) {
Integer cur = next.get(pool[lo]);
if (cur == null || ops + 1 < cur) next.put(pool[lo], ops + 1);
}
}
dp = next;
}
int best = Integer.MAX_VALUE;
for (int ops : dp.values()) best = Math.min(best, ops);
return best == Integer.MAX_VALUE ? -1 : best;
}C++
int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
vector<int> pool = arr2;
sort(pool.begin(), pool.end());
map<int, int> dp;
dp[-1] = 0;
for (int v : arr1) {
map<int, int> next;
for (auto& e : dp) {
int prev = e.first, ops = e.second;
if (v > prev) {
if (!next.count(v) || ops < next[v]) next[v] = ops;
}
auto it = upper_bound(pool.begin(), pool.end(), prev);
if (it != pool.end()) {
int cand = *it;
if (!next.count(cand) || ops + 1 < next[cand]) next[cand] = ops + 1;
}
}
dp = next;
}
int best = INT_MAX;
for (auto& e : dp) best = min(best, e.second);
return best == INT_MAX ? -1 : best;
}JavaScript
var makeArrayIncreasing = function(arr1, arr2) {
var pool = arr2.slice();
pool.sort(function(a, b) { return a - b; });
var INF = 1000000000;
var dp = { "-1": 0 };
for (var i = 0; i < arr1.length; i++) {
var next = {};
var keys = Object.keys(dp);
for (var t = 0; t < keys.length; t++) {
var prev = parseInt(keys[t], 10);
var ops = dp[keys[t]];
if (arr1[i] > prev) {
var k1 = String(arr1[i]);
if (next[k1] === undefined || ops < next[k1]) next[k1] = ops;
}
var lo = 0, hi = pool.length;
while (lo < hi) {
var mid = (lo + hi) >> 1;
if (pool[mid] > prev) hi = mid; else lo = mid + 1;
}
if (lo < pool.length) {
var k2 = String(pool[lo]);
if (next[k2] === undefined || ops + 1 < next[k2]) next[k2] = ops + 1;
}
}
dp = next;
}
var best = INF;
var finalKeys = Object.keys(dp);
for (t = 0; t < finalKeys.length; t++) if (dp[finalKeys[t]] < best) best = dp[finalKeys[t]];
return best === INF ? -1 : best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming