Make Array Strictly Increasing
Problem
Given two integer arrays arr1 and arr2, in one operation you may pick an index i of arr1 and replace arr1[i] with any element of arr2. Return the minimum number of operations needed to make arr1 strictly increasing, or -1 if it is impossible.
arr1 = [1, 5, 3, 6, 7], arr2 = [1, 3, 2, 4]1import bisect
def make_array_increasing(arr1, arr2):
arr2 = sorted(set(arr2))
# dp: maps "last value of prefix" -> min operations
dp = {-1: 0}
for x in arr1:
ndp = {}
for last, cost in dp.items():
# Option 1: keep arr1[i] if it stays increasing
if x > last:
ndp[x] = min(ndp.get(x, 10**9), cost)
# Option 2: replace with smallest arr2 value > last
j = bisect.bisect_right(arr2, last)
if j < len(arr2):
v = arr2[j]
ndp[v] = min(ndp.get(v, 10**9), cost + 1)
dp = ndp
if not dp:
return -1
return min(dp.values())function makeArrayIncreasing(arr1, arr2) {
arr2 = [...new Set(arr2)].sort((a, b) => a - b);
let dp = new Map([[-Infinity, 0]]);
for (const x of arr1) {
const ndp = new Map();
for (const [last, cost] of dp) {
if (x > last) {
ndp.set(x, Math.min(ndp.get(x) ?? Infinity, cost));
}
let lo = 0, hi = arr2.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (arr2[mid] > last) hi = mid; else lo = mid + 1;
}
if (lo < arr2.length) {
const v = arr2[lo];
ndp.set(v, Math.min(ndp.get(v) ?? Infinity, cost + 1));
}
}
dp = ndp;
if (dp.size === 0) return -1;
}
return Math.min(...dp.values());
}class Solution {
public int makeArrayIncreasing(int[] arr1, int[] arr2) {
TreeSet<Integer> set = new TreeSet<>();
for (int v : arr2) set.add(v);
Integer[] a2 = set.toArray(new Integer[0]);
Map<Integer, Integer> dp = new HashMap<>();
dp.put(Integer.MIN_VALUE, 0);
for (int x : arr1) {
Map<Integer, Integer> ndp = new HashMap<>();
for (Map.Entry<Integer, Integer> e : dp.entrySet()) {
int last = e.getKey(), cost = e.getValue();
if (x > last)
ndp.merge(x, cost, Math::min);
Integer v = set.higher(last);
if (v != null)
ndp.merge(v, cost + 1, Math::min);
}
dp = ndp;
if (dp.isEmpty()) return -1;
}
int best = Integer.MAX_VALUE;
for (int c : dp.values()) best = Math.min(best, c);
return best;
}
}int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
sort(arr2.begin(), arr2.end());
arr2.erase(unique(arr2.begin(), arr2.end()), arr2.end());
map<int, int> dp{{INT_MIN, 0}};
for (int x : arr1) {
map<int, int> ndp;
for (auto& [last, cost] : dp) {
if (x > last) {
if (!ndp.count(x) || ndp[x] > cost) ndp[x] = cost;
}
auto it = upper_bound(arr2.begin(), arr2.end(), last);
if (it != arr2.end()) {
int v = *it;
if (!ndp.count(v) || ndp[v] > cost + 1) ndp[v] = cost + 1;
}
}
dp = ndp;
if (dp.empty()) return -1;
}
int best = INT_MAX;
for (auto& [k, c] : dp) best = min(best, c);
return best;
}Explanation
As we walk through arr1 left to right, the only thing that matters about the past is the last value we ended on and how many replacements it took to get there. So the state we carry is a map from "end value" to "minimum operations".
The dp map starts as { -∞ → 0 }, meaning before we begin, the prefix ends below everything and cost nothing. For each new element x we build a fresh map ndp by considering every previous end value last.
There are two choices. Keep x if x > last (no extra cost). Or replace it: we take the smallest value in the sorted, de-duplicated arr2 that is strictly greater than last (found with binary search) and pay one operation. We always keep the cheapest cost for each resulting end value.
If at any point dp becomes empty, no choice kept the array increasing, so the answer is -1. Otherwise the final answer is the smallest cost left in the map after the last element.
Example: for arr1 = [1,5,3,6,7] with arr2 = [1,3,2,4], the dp explores keeping or swapping each element and finds the cheapest path needs just one replacement (swapping the out-of-order 3 for a value from arr2), so the answer is 1.