1187. Make Array Strictly Increasing - Solution

The 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.

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.

Python

from bisect import bisect_right

class Solution:
    def makeArrayIncreasing(self, arr1, arr2):
        arr2.sort()
        n = len(arr1)
        dp = [float('inf')] * (n + 1)
        dp[0] = 0
        for i in range(1, n + 1):
            for j in range(i - 1, -1, -1):
                if j == 0 or arr1[j - 1] < arr1[i - 1]:
                    dp[i] = min(dp[i], dp[j])
                pos = bisect_right(arr2, arr1[j - 1])
                if pos < len(arr2):
                    dp[i] = min(dp[i], dp[j] + 1)
        return -1 if dp[n] == float('inf') else dp[n]

# Example usage
sol = Solution()
arr1 = [1, 5, 3, 6, 7]
arr2 = [1, 3, 2, 4]
result = sol.makeArrayIncreasing(arr1, arr2)
print(result)

Java

import java.util.*;

public class Solution {
    public int makeArrayIncreasing(int[] arr1, int[] arr2) {
        Arrays.sort(arr2);
        int n = arr1.length;
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (j == 0 || arr1[j - 1] < arr1[i - 1]) {
                    dp[i] = Math.min(dp[i], dp[j]);
                }
                int pos = Arrays.binarySearch(arr2, arr1[j - 1] + 1);
                if (pos < 0) pos = -pos - 1;
                if (pos < arr2.length) {
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }
        return dp[n] == Integer.MAX_VALUE ? -1 : dp[n];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] arr1 = {1, 5, 3, 6, 7};
        int[] arr2 = {1, 3, 2, 4};
        int result = sol.makeArrayIncreasing(arr1, arr2);
        System.out.println(result);
    }
}

C++

#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

class Solution {
public:
    int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
        sort(arr2.begin(), arr2.end());
        int n = arr1.size(), m = arr2.size();
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (arr1[j - 1] < arr1[i - 1]) {
                    dp[i] = min(dp[i], dp[j]);
                }
                int pos = lower_bound(arr2.begin(), arr2.end(), arr1[j - 1] + 1) - arr2.begin();
                if (pos < m) {
                    dp[i] = min(dp[i], dp[j] + 1);
                }
            }
        }
        return dp[n] == INT_MAX ? -1 : dp[n];
    }
};

int main() {
    Solution sol;
    vector<int> arr1 = {1, 5, 3, 6, 7};
    vector<int> arr2 = {1, 3, 2, 4};
    int result = sol.makeArrayIncreasing(arr1, arr2);
    cout << result << endl;
    return 0;
}

JavaScript

const makeArrayIncreasing = (arr1, arr2) => {
    arr2.sort((a, b) => a - b);
    const n = arr1.length;
    const dp = new Array(n + 1).fill(Infinity);
    dp[0] = 0;
    for (let i = 1; i <= n; i++) {
        for (let j = i - 1; j >= 0; j--) {
            if (j === 0 || arr1[j - 1] < arr1[i - 1]) {
                dp[i] = Math.min(dp[i], dp[j]);
            }
            let pos = bisectRight(arr2, arr1[j - 1]);
            if (pos < arr2.length) {
                dp[i] = Math.min(dp[i], dp[j] + 1);
            }
        }
    }
    return dp[n] === Infinity ? -1 : dp[n];
};

const bisectRight = (arr, x) => {
    let lo = 0, hi = arr.length;
    while (lo < hi) {
        const mid = Math.floor((lo + hi) / 2);
        if (arr[mid] <= x) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return lo;
};

// Example usage
const arr1 = [1, 5, 3, 6, 7];
const arr2 = [1, 3, 2, 4];
console.log(makeArrayIncreasing(arr1, arr2));

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

int binarySearch(int* arr, int size, int x) {
    int left = 0, right = size - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] <= x)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return left < size ? left : -1;
}

int makeArrayIncreasing(int* arr1, int arr1Size, int* arr2, int arr2Size) {
    qsort(arr2, arr2Size, sizeof(int), compare);
    int* dp = malloc((arr1Size + 1) * sizeof(int));
    dp[0] = 0;
    for (int i = 1; i <= arr1Size; ++i) {
        dp[i] = INT_MAX;
        if (arr1[i - 1] > arr1[i - 2]) {
            dp[i] = dp[i - 1];
        }
        int pos = binarySearch(arr2, arr2Size, arr1[i - 2]);
        if (pos != -1) {
            dp[i] = fmin(dp[i], dp[i - 1] + 1);
        }
    }
    int result = dp[arr1Size];
    free(dp);
    return result == INT_MAX ? -1 : result;
}

int main() {
    int arr1[] = {1, 5, 3, 6, 7};
    int arr2[] = {1, 3, 2, 4};
    int result = makeArrayIncreasing(arr1, sizeof(arr1) / sizeof(arr1[0]), arr2, sizeof(arr2) / sizeof(arr2[0]));
    printf("%d\n", result);
    return 0;
}

using System;

public class Solution {
    public int MakeArrayIncreasing(int[] arr1, int[] arr2) {
        Array.Sort(arr2);
        int n = arr1.Length;
        int[] dp = new int[n + 1];
        Array.Fill(dp, int.MaxValue);
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (j == 0 || arr1[j - 1] < arr1[i - 1]) {
                    dp[i] = Math.Min(dp[i], dp[j]);
                }
                int pos = Array.BinarySearch(arr2, arr1[j - 1] + 1);
                if (pos < 0) pos = ~pos;
                if (pos < arr2.Length) {
                    dp[i] = Math.Min(dp[i], dp[j] + 1);
                }
            }
        }
        return dp[n] == int.MaxValue ? -1 : dp[n];
    }

    public static void Main(string[] args) {
        var sol = new Solution();
        int[] arr1 = {1, 5, 3, 6, 7};
        int[] arr2 = {1, 3, 2, 4};
        int result = sol.MakeArrayIncreasing(arr1, arr2);
        Console.WriteLine(result);
    }
}

The Python solution employs the bisect module for efficient searching and maintains a dynamic programming array to store minimal operations required at every step to keep arr1 strictly increasing.

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.

TypeScript

function makeArrayIncreasing(arr1: number[], arr2: number[]): number {
    arr2.sort((a, b) => a - b);
    let m = 0;
    for (const x of arr2) {
        if (m === 0 || x !== arr2[m - 1]) {
            arr2[m++] = x;
        }
    }
    arr2 = arr2.slice(0, m);
    const inf = 1 << 30;
    arr1 = [-inf, ...arr1, inf];
    const n = arr1.length;
    const f: number[] = new Array(n).fill(inf);
    f[0] = 0;
    const search = (arr: number[], x: number): number => {
        let l = 0;
        let r = arr.length;
        while (l < r) {
            const mid = (l + r) >> 1;
            if (arr[mid] >= x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    };
    for (let i = 1; i < n; ++i) {
        if (arr1[i - 1] < arr1[i]) {
            f[i] = f[i - 1];
        }
        const j = search(arr2, arr1[i]);
        for (let k = 1; k <= Math.min(i - 1, j); ++k) {
            if (arr1[i - k - 1] < arr2[j - k]) {
                f[i] = Math.min(f[i], f[i - k - 1] + k);
            }
        }
    }
    return f[n - 1] >= inf ? -1 : f[n - 1];
}

func makeArrayIncreasing(arr1 []int, arr2 []int) int {
	sort.Ints(arr2)
	m := 0
	for _, x := range arr2 {
		if m == 0 || x != arr2[m-1] {
			arr2[m] = x
			m++
		}
	}
	arr2 = arr2[:m]
	const inf = 1 << 30
	arr1 = append([]int{-inf}, arr1...)
	arr1 = append(arr1, inf)
	n := len(arr1)
	f := make([]int, n)
	for i := range f {
		f[i] = inf
	}
	f[0] = 0
	for i := 1; i < n; i++ {
		if arr1[i-1] < arr1[i] {
			f[i] = f[i-1]
		}
		j := sort.SearchInts(arr2, arr1[i])
		for k := 1; k <= min(i-1, j); k++ {
			if arr1[i-k-1] < arr2[j-k] {
				f[i] = min(f[i], f[i-k-1]+k)
			}
		}
	}
	if f[n-1] >= inf {
		return -1
	}
	return f[n-1]
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
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	–

Complexity analysis

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

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.

Make Array Strictly Increasing solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming with Binary Search

Approach 2: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Make Array Strictly Increasing solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming with Binary Search

Approach 2: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems