Make Array Strictly Increasing — Hard Problem & Solution

In one operation you may replace any element of arr1 with any element of arr2 — elements of arr2 may be reused.

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 <= 2000
0 <= arr1[i], arr2[i] <= 10^9

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 arr2 once.
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 -1 if 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 arr2 may be reused any number of times.
An empty state map means the array cannot be fixed, which is the -1 case.

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 -1

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue