Scale Engineer

Make Array Strictly Increasing

Hard
#1112Time: O(N * (N + M)). The outer loop runs N times. Inside, updating states takes O(N + M) due to the optimized single-pass scan over `dp` states and `arr2`.Space: O(N), where N is the length of `arr1`. The `dp` map stores at most `N+1` entries.
Patterns
Dynamic Programming
Algorithms
Binary SearchSorting
Data structures
Array

Prompt

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:

5

Example 2:

5

Example 3:

arr1

 

Constraints:

  • 1 <= arr1.length, arr2.length <= 2000
  • 0 <= arr1[i], arr2[i] <= 10^9

 

Approaches

3 approaches with complexity analysis and trade-offs.

The most efficient solution optimizes the iterative DP approach. In the previous approach, for each state in our dp map, we performed a binary search on arr2. This leads to a log M factor in the complexity. We can eliminate this factor by observing a property of our DP states. For a given number of operations ops, the minimum last element dp[ops] is non-increasing as ops increases. This monotonicity allows us to use a two-pointer/single-pass technique to find all necessary replacement values from arr2 for a given arr1 element, reducing the complexity of this step from O(N log M) to O(N + M).

Algorithm

This approach builds upon the iterative DP but optimizes the replacement step. The key observation is that for a given DP map dp, if we sort the entries by the number of operations ops, the corresponding values min_last_element are non-increasing. This property allows us to replace the repeated binary searches with a single pass.

  1. Preprocessing: Sort arr2 and remove duplicates.
  2. DP State: Same as the previous approach, a map dp where dp[k] = v.
  3. Initialization: dp = {0: -1}. A TreeMap is suitable here to keep the keys (operations) sorted.
  4. Iteration: For each element x in arr1:
    • Create a new_dp map.
    • Keep x: Iterate through (ops, prev_val) in dp. If x > prev_val, update new_dp[ops] with x.
    • Replace x (Optimized): Iterate through (ops, prev_val) in dp again (in sorted order of ops). Use a pointer k for arr2. Since prev_val is non-increasing as ops increases, the pointer k for finding the smallest element in arr2 greater than prev_val only needs to move forward. This amortizes the search for all ops to a single O(M) pass over arr2.
    • Merge the results from the 'keep' and 'replace' steps into new_dp.
    • Update dp = new_dp.
  5. Result: The minimum key in the final dp map is the answer.

Walkthrough

The overall structure is the same as the standard iterative DP. We use a TreeMap for our dp map to automatically keep the states sorted by the number of operations. This is crucial for the optimization.

For each element x in arr1, we build a new_dp map.

The 'keep' logic remains the same: for each (ops, prev) in dp, if x > prev, we can form a state (ops, x) in new_dp.

The 'replace' logic is optimized. Instead of a binary search for each (ops, prev) pair, we do one combined pass. We iterate through the dp map's entries, which are sorted by ops. Because of this, the prev values we process will be non-increasing. We use a pointer, k, for sortedUniqueArr2. For each prev, we advance k until arr2[k] > prev. Since prev is non-increasing, k never needs to be reset; it only moves forward across arr2. This way, we find the optimal replacement for all ops in a total of O(N + M) time for each x.

By combining the 'keep' and 'replace' updates, we can build the new_dp map for the current x and then continue to the next element.

import java.util.*; class Solution {    public int makeArrayIncreasing(int[] arr1, int[] arr2) {        Set<Integer> set = new TreeSet<>();        for (int val : arr2) {            set.add(val);        }        int[] sortedUniqueArr2 = new int[set.size()];        int i = 0;        for (int val : set) {            sortedUniqueArr2[i++] = val;        }         // Use TreeMap to keep ops sorted        TreeMap<Integer, Integer> dp = new TreeMap<>();        dp.put(0, -1);         for (int x : arr1) {            TreeMap<Integer, Integer> newDp = new TreeMap<>();            // Option 1: Keep x            for (Map.Entry<Integer, Integer> entry : dp.entrySet()) {                if (x > entry.getValue()) {                    int ops = entry.getKey();                    int prev = x;                    newDp.put(ops, Math.min(newDp.getOrDefault(ops, Integer.MAX_VALUE), prev));                }            }             // Option 2: Replace x (Optimized)            for (Map.Entry<Integer, Integer> entry : dp.entrySet()) {                int ops = entry.getKey();                int prev = entry.getValue();                                int replaceIndex = findFirstGreater(sortedUniqueArr2, prev);                if (replaceIndex < sortedUniqueArr2.length) {                    int val = sortedUniqueArr2[replaceIndex];                    newDp.put(ops + 1, Math.min(newDp.getOrDefault(ops + 1, Integer.MAX_VALUE), val));                }            }                        if (newDp.isEmpty()) {                return -1;            }            dp = newDp;        }         return dp.firstKey();    }     private int findFirstGreater(int[] arr, int val) {        int left = 0, right = arr.length;        while (left < right) {            int mid = left + (right - left) / 2;            if (arr[mid] > val) {                right = mid;            } else {                left = mid + 1;            }        }        return left;    }}// Note: The provided code snippet for this section still uses binary search for clarity.// A true O(N*(N+M)) implementation would replace the inner loop's binary search with a single-pass pointer.// For example:// int k = 0;// for (Map.Entry<Integer, Integer> entry : dp.entrySet()) {//     int ops = entry.getKey();//     int prev = entry.getValue();//     while (k < sortedUniqueArr2.length && sortedUniqueArr2[k] <= prev) {//         k++;//     }//     if (k < sortedUniqueArr2.length) {//         newDp.put(ops + 1, Math.min(newDp.getOrDefault(ops + 1, Integer.MAX_VALUE), sortedUniqueArr2[k]));//     }// }

Complexity

Time

O(N * (N + M)). The outer loop runs N times. Inside, updating states takes O(N + M) due to the optimized single-pass scan over `dp` states and `arr2`.

Space

O(N), where N is the length of `arr1`. The `dp` map stores at most `N+1` entries.

Trade-offs

Pros

  • Most efficient time complexity among the discussed approaches.

  • Handles the problem constraints comfortably.

Cons

  • The implementation logic is more complex than the standard iterative DP.

Solutions

public class Solution {    public int MakeArrayIncreasing(int[] arr1, int[] arr2) {        Array.Sort(arr2);        int m = 0;        foreach(int x in arr2) {            if (m == 0 || x != arr2[m - 1]) {                arr2[m++] = x;            }        }        int inf = 1 << 30;        int[] arr = new int[arr1.Length + 2];        arr[0] = -inf;        arr[arr.Length - 1] = inf;        for (int i = 0; i < arr1.Length; ++i) {            arr[i + 1] = arr1[i];        }        int[] f = new int[arr.Length];        Array.Fill(f, inf);        f[0] = 0;        for (int i = 1; i < arr.Length; ++i) {            if (arr[i - 1] < arr[i]) {                f[i] = f[i - 1];            }            int j = search(arr2, arr[i], m);            for (int k = 1; k <= Math.Min(i - 1, j); ++k) {                if (arr[i - k - 1] < arr2[j - k]) {                    f[i] = Math.Min(f[i], f[i - k - 1] + k);                }            }        }        return f[arr.Length - 1] >= inf ? -1 : f[arr.Length - 1];    }    private int search(int[] nums, int x, int n) {        int l = 0, r = n;        while (l < r) {            int mid = (l + r) >> 1;            if (nums[mid] >= x) {                r = mid;            } else {                l = mid + 1;            }        }        return l;    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem