1187. Make Array Strictly Increasing

Description

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.

Idea

Intuition:

For any operation, we need to consider the smallest element in arr2. Thus, we sort the arr2 first.

Core idea:

Run dfs with two branches:

1. Keep the current element in arr1
2. Add one replacement

Finally return the minimum of these branches.

Solution

class Solution {
public:
    const static int max_n = 2001;
    int dp[max_n][max_n] = {};
    int dfs(vector<int>& arr1, vector<int>& arr2, int index1, int index2, int prev) {
        if (index1 >= arr1.size()) {
            return 0;
        }
        index2 = upper_bound(begin(arr2) + index2, end(arr2), prev) - begin(arr2);
        int r1 = max_n, r2 = max_n;
        if (!dp[index1][index2]) {
            if (index2 < arr2.size()) {
                r2 = 1 + dfs(arr1, arr2, index1 + 1, index2, arr2[index2]);
            }
            if (prev < arr1[index1]) {
                r1 = dfs(arr1, arr2, index1 + 1, index2, arr1[index1]);
            }
            dp[index1][index2] = min(r1, r2);
        }
        return dp[index1][index2];
    }
    
    int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr) {
        std::set<int> aset(arr.begin(), arr.end());
        vector<int> arr2(aset.begin(), aset.end());
        int res = dfs(arr1, arr2, 0, 0, INT_MIN);
        return res == max_n ? -1 : res;
    }
};