# Make Array Strictly Increasing
**Difficulty:** HARD
[External](https://leetcode.com/problems/make-array-strictly-increasing)
Canonical: https://scaleengineer.com/dsa/problems/make-array-strictly-increasing
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## 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`

# Approaches
## Top-Down Dynamic Programming with Memoization
This approach solves the problem using a top-down dynamic programming technique, which is often a natural way to translate a recursive decision-making process into an efficient algorithm. We define a recursive function that explores the two choices for each element in `arr1`: either keep it or replace it with an element from `arr2`. To avoid recomputing results for the same subproblems (same index `i` and same previous value `prev`), we use memoization.
**Time:** O(N * U * log M), where U is the number of unique values in `arr1` and `arr2` (at most N+M). For each state `(i, prev)`, we perform a binary search on `arr2` which takes `O(log M)` time. · **Space:** O(N * (N+M)) in the worst case for the memoization table, where N and M are the lengths of `arr1` and `arr2`. This is because there are N possible indices and O(N+M) possible values for `prev`.
**Pros:** Conceptually straightforward, directly modeling the decision process.; Can be a good starting point before optimizing to an iterative solution.
**Cons:** The state space can be large. The `prev` value can be any element from `arr1` or `arr2`, leading to `O(N * (N+M))` states.; Using a map for memoization for each index `i` can have performance overhead compared to array-based DP.; The time complexity is higher than iterative DP approaches.
### Explanation
The core of this method is a recursive helper function, let's call it `dfs(i, prev)`. The parameter `i` represents the current index in `arr1` we are considering, and `prev` is the value of the element at index `i-1` in the modified `arr1`. The function's goal is to find the minimum number of swaps for the subarray `arr1[i:]`.

To make decisions, for `arr1[i]`, we compare it with `prev`. 
- If we choose to **keep** `arr1[i]`, it must be greater than `prev`. The number of operations doesn't increase, and we move to the next state `dfs(i + 1, arr1[i])`.
- If we choose to **replace** `arr1[i]`, we must pick a value from `arr2` that is greater than `prev`. To minimize future constraints, it's always optimal to pick the smallest possible value from `arr2` that satisfies this condition. We can find this value efficiently using binary search on a sorted `arr2`. This choice costs one operation, and we proceed to the next state `dfs(i + 1, replacement_value)`.

The final answer for `dfs(i, prev)` is the minimum of the outcomes of these two choices. If a choice is invalid (e.g., `arr1[i] <= prev` for the 'keep' option, or no suitable replacement found in `arr2`), it's considered to have an infinite cost.

To handle the large range of possible values for `prev`, which makes a simple 2D array for memoization infeasible, we can use a `Map<Integer, Integer>` for each index `i`. `memo[i]` would map a `prev` value to the minimum operations calculated.

```java
import java.util.*;

class Solution {
    Map<Integer, Integer>[] memo;
    int[] arr1, arr2;
    final int INF = 2001; // A value larger than any possible answer

    public int makeArrayIncreasing(int[] arr1, int[] arr2) {
        this.arr1 = arr1;
        // Sort and remove duplicates from arr2
        Set<Integer> set = new TreeSet<>();
        for (int val : arr2) {
            set.add(val);
        }
        this.arr2 = new int[set.size()];
        int k = 0;
        for (int val : set) {
            this.arr2[k++] = val;
        }

        memo = new HashMap[arr1.length];
        for (int i = 0; i < arr1.length; i++) {
            memo[i] = new HashMap<>();
        }

        int result = dfs(0, -1);
        return result >= INF ? -1 : result;
    }

    private int dfs(int i, int prev) {
        if (i == arr1.length) {
            return 0;
        }
        if (memo[i].containsKey(prev)) {
            return memo[i].get(prev);
        }

        int cost = INF;

        // Option 1: Keep arr1[i]
        if (arr1[i] > prev) {
            cost = dfs(i + 1, arr1[i]);
        }

        // Option 2: Replace arr1[i]
        int replaceIndex = findFirstGreater(prev);
        if (replaceIndex < arr2.length) {
            cost = Math.min(cost, 1 + dfs(i + 1, arr2[replaceIndex]));
        }

        memo[i].put(prev, cost);
        return cost;
    }

    // Find the index of the first element in arr2 > val
    private int findFirstGreater(int val) {
        int left = 0, right = arr2.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr2[mid] > val) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}
```
### Algorithm
The problem can be modeled using recursion with memoization. We define a function `solve(i, prev)` that calculates the minimum operations to make the subarray `arr1[i:]` strictly increasing, given that the element before `arr1[i]` has the value `prev`.

1.  **Preprocessing**: Sort `arr2` and remove duplicates to enable efficient searching for replacement values. This can be done in `O(M log M)` time.
2.  **Recursive Function `solve(i, prev)`**:
    *   **Base Case**: If `i` reaches the end of `arr1` (`i == arr1.length`), it means we have successfully made the entire array increasing. We need 0 more operations, so return 0.
    *   **Memoization**: Use a 2D memoization table, `memo[i][prev_val_index]`, to store the results of `solve(i, prev)`. Since `prev` can be a large number, we can either use a map for memoization (`Map<Integer, Integer>[] memo`) or discretize the values from `arr1` and `arr2` to map them to indices. The latter is more complex to implement.
    *   **Recursive Step**: At index `i`, we have two choices:
        a. **Keep `arr1[i]`**: This is possible only if `arr1[i] > prev`. The cost would be `solve(i + 1, arr1[i])`.
        b. **Replace `arr1[i]`**: We need to find the smallest element in `arr2` that is strictly greater than `prev`. We can find this using binary search (`upper_bound`) on the processed `arr2`. If such an element `val` exists, the cost is `1 + solve(i + 1, val)`.
    *   The function returns the minimum of the costs from the valid choices. If no choice is possible, return a large value representing infinity.
3.  **Initial Call**: The recursion starts with `solve(0, -1)`.
4.  **Result**: If the final result is infinity, it's impossible to make the array increasing, so return -1. Otherwise, return the result.

## Iterative Bottom-Up DP
A more efficient method is to use iterative (bottom-up) dynamic programming. This approach avoids recursion and often leads to better performance and space usage. The key idea is to change the DP state. Instead of `(index, prev_value)`, we build up a set of states representing `(number_of_operations, min_last_element_value)`. We process `arr1` one element at a time, and for each element, we calculate the new set of possible states based on the states from the previous step.
**Time:** O(N^2 * log M). The outer loop runs N times. The inner loop runs over the `dp` map, which has size at most O(N). Inside, a binary search on `arr2` takes O(log M). · **Space:** O(N), where N is the length of `arr1`. The `dp` map can have at most `N+1` entries at any point.
**Pros:** More efficient than the recursive approach.; Space complexity is better, typically `O(N)` instead of `O(N * (N+M))`.; Iterative nature avoids recursion depth issues.
**Cons:** The time complexity is still polynomial, dominated by the nested loops and binary search.; Requires careful state transition logic to ensure correctness.
### Explanation
We maintain a map `dp` where a key-value pair `ops: val` signifies that it's possible to have a strictly increasing prefix ending with value `val` using `ops` operations. We want to minimize `val` for any given `ops`.

We initialize `dp` with `{0: -1}` to represent the state before processing any element of `arr1`.

Then, for each element `x` in `arr1`, we compute a `new_dp` map. For every state `(ops, prev_val)` in the current `dp`:
- **Keep `x`**: If `x > prev_val`, we have a new potential state: `ops` operations ending with value `x`. We update `new_dp[ops]` to be `x` if it's better than the existing value for `ops` in `new_dp`.
- **Replace `x`**: We can use one more operation (`ops + 1`). We find the smallest value in `arr2` greater than `prev_val` (let's call it `swap_val`). This gives a potential state: `ops + 1` operations ending with `swap_val`. We update `new_dp[ops + 1]` accordingly.

After iterating through all states in `dp`, `new_dp` becomes the `dp` for the next element of `arr1`. If `new_dp` is empty at any stage, it means we've hit a dead end and no solution is possible.

Finally, after processing all of `arr1`, the answer is the smallest key (number of operations) in the final `dp` map.

```java
import java.util.*;

class Solution {
    public int makeArrayIncreasing(int[] arr1, int[] arr2) {
        // Sort and remove duplicates from arr2
        Set<Integer> set = new TreeSet<>();
        for (int val : arr2) {
            set.add(val);
        }
        int[] sortedUniqueArr2 = new int[set.size()];
        int k = 0;
        for (int val : set) {
            sortedUniqueArr2[k++] = val;
        }

        Map<Integer, Integer> dp = new HashMap<>();
        dp.put(0, -1); // {operations: min_last_element}

        for (int x : arr1) {
            Map<Integer, Integer> newDp = new HashMap<>();
            for (Map.Entry<Integer, Integer> entry : dp.entrySet()) {
                int ops = entry.getKey();
                int prev = entry.getValue();

                // Option 1: Keep x
                if (x > prev) {
                    newDp.put(ops, Math.min(newDp.getOrDefault(ops, Integer.MAX_VALUE), x));
                }

                // Option 2: Replace x
                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;
        }

        int minOps = Integer.MAX_VALUE;
        for (int ops : dp.keySet()) {
            minOps = Math.min(minOps, ops);
        }

        return minOps == Integer.MAX_VALUE ? -1 : minOps;
    }

    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;
    }
}
```
### Algorithm
This approach uses bottom-up dynamic programming. Instead of tracking the `prev` value directly in the state, we track the number of operations.

1.  **Preprocessing**: Sort `arr2` and remove duplicates in `O(M log M)` time.
2.  **DP State**: We use a map, `dp`, where `dp[k] = v` means that the minimum possible value of the last element is `v` after making a strictly increasing prefix of the currently processed part of `arr1` using `k` operations.
3.  **Initialization**: Start with `dp = {0: -1}`. This signifies that before processing `arr1`, we have a 0-length prefix with 0 operations, and the 'previous' element is -1.
4.  **Iteration**: Iterate through each element `x` of `arr1`.
    *   For each `x`, create a `new_dp` map to store the possible states after processing `x`.
    *   Iterate through each `(ops, prev_val)` pair in the current `dp` map.
        a. **Keep `x`**: If `x > prev_val`, we can keep `x`. This results in a state with `ops` operations. We update `new_dp[ops]` with `min(current_new_dp_val, x)`.
        b. **Replace `x`**: Find the smallest element `val` in `arr2` that is `> prev_val` using binary search. This costs one operation. We update `new_dp[ops + 1]` with `min(current_new_dp_val, val)`.
    *   After considering all states in the old `dp`, replace `dp` with `new_dp`.
5.  **Result**: After iterating through all of `arr1`, the final `dp` map contains all possible operation counts and their corresponding minimum last elements. The minimum key in this map is the minimum number of operations required for the whole array. If the final `dp` is empty, no solution exists, so return -1.

## Optimized Iterative DP
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)`.
**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.
**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.
### Explanation
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.

```java
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]));
//     }
// }
```
### 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.

# Solutions
### CSharp

```csharp
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;
    }
}
```

### Java

```java
class Solution {
public
  int makeArrayIncreasing(int[] arr1, int[] arr2) {
    Arrays.sort(arr2);
    int m = 0;
    for (int x : arr2) {
      if (m == 0 || x != arr2[m - 1]) {
        arr2[m++] = x;
      }
    }
    final int inf = 1 << 30;
    int[] arr = new int[arr1.length + 2];
    arr[0] = -inf;
    arr[arr.length - 1] = inf;
    System.arraycopy(arr1, 0, arr, 1, arr1.length);
    int[] f = new int[arr.length];
    Arrays.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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int makeArrayIncreasing(vector<int> &arr1, vector<int> &arr2) {
    sort(arr2.begin(), arr2.end());
    arr2.erase(unique(arr2.begin(), arr2.end()), arr2.end());
    const int inf = 1 << 30;
    arr1.insert(arr1.begin(), -inf);
    arr1.push_back(inf);
    int n = arr1.size();
    vector<int> f(n, inf);
    f[0] = 0;
    for (int i = 1; i < n; ++i) {
      if (arr1[i - 1] < arr1[i]) {
        f[i] = f[i - 1];
      }
      int j = lower_bound(arr2.begin(), arr2.end(), arr1[i]) - arr2.begin();
      for (int 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);
        }
      }
    }
    return f[n - 1] >= inf ? -1 : f[n - 1];
  }
};

```

### Python

```python
class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int: arr2 . sort() m = 0 for x in arr2: if m == 0 or x != arr2[m - 1]: arr2[m] = x m += 1 arr2 = arr2[: m] arr = [- inf] + arr1 + [inf] n = len(arr) f = [inf] * n f[0] = 0 for i in range(1, n): if arr[i - 1] < arr[i]: f[i] = f[i - 1] j = bisect_left(arr2, arr[i]) for k in range(1, min(i - 1, j) + 1): if arr[i - k - 1] < arr2[j - k]: f[i] = min(f[i], f[i - k - 1] + k) return - 1 if f[n - 1] >= inf else f[n - 1]

```