Leetcode 1187: Make Array Strictly Increasing

https://leetcode.com/problems/make-array-strictly-increasing/description/

Notes:

One way to solve this problem is to link this problem to the Longest Increasing Sub-sequence (LIS). The only difference is that, for each dp[j] < dp[i], we need to check whether there are enough sorted elements (i - j - 1) in arr2 to replace all the corresponding elements from j to i (exclusively) in arr1.

See the code below:

class Solution {
public:
    int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
        int len = arr1.size();
        arr1.insert(arr1.begin(), INT_MIN);//solve boundary conditions
        arr1.push_back(INT_MAX);
        vector<int> dp(len+2, INT_MAX);//dp[i]: the minimum operations to make arr1[0] to arr1[i] sorted
        dp[0] = 0;
        sort(arr2.begin(), arr2.end());
        arr2.resize(unique(arr2.begin(), arr2.end()) - arr2.begin());//remove duplicates
        for(int i=1; i<len+2; ++i) {
            for(int j=0; j<i; ++j) {
                if(arr1[j] < arr1[i] && dp[j] != INT_MAX) {//LIS algorithm
                    int opr = replace(arr1, arr2, j, i);
                    if(opr >= 0) dp[i] = min(dp[i], dp[j] + opr);
                }
            }
        }
        return dp[len+1] == INT_MAX? -1 : dp[len+1];
    }
private:
    int replace(vector<int> &v1, vector<int> &v2, int left, int right) {//replace (left, right) of arr1 by the sorted arr2
        if(left + 1 == right) return 0;
        int id = upper_bound(v2.begin(), v2.end(), v1[left]) - v2.begin();
        id += right - left - 2;//the total length is (right - left - 1), now id is the index of the last element used for replacing
        if(id < v2.size() && v2[id] < v1[right]) return right - left - 1;
        return -1;
    }
};