Leetcode 1187: Make Array Strictly Increasing

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

Problem Analysis:

In the constraints, we can see the array arr1 and arr2 is small, their lengths ≤ 2000, so we can use dynamic programming algorithm to deal with it.

We iterate items in the array arr1, for ith item of arr1, we use dp to record the possible value we can place at this position, and record the number of replace operations used, this number we will update with the minimum number of replace operations when meet again.

For i+1th item of arr1, if its value larger than ith item, then:

1. there is no replace operation needed
2. find a item in arr2 that larger than ith item of arr1 and smaller than i+1th item of arr1, and use a replace operation

If value of i+1th item of arr1 not larger than ith item, we need to make a replace operation.

After this iteration, we can get the minimum number of replace operations we need to make the array strictly increasing.

Solution

class Solution {
public:
    int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
        sort(begin(arr2), end(arr2));
        unordered_map<int,int> dp;
        dp[-1] = 0;
        for (const auto& item: arr1) {
            unordered_map<int,int> tmp;
            for (const auto& [key, value]: dp) {
                if (item > key){
                    int lastCount = tmp.count(item) > 0 ? tmp[item] : INT_MAX;
                    tmp[item] = min(lastCount, value);
                }
                auto it = upper_bound(begin(arr2), end(arr2), key);
                if (it != arr2.end()) {
                    int lastCount = tmp.count(*it) > 0 ? tmp[*it] : INT_MAX;
                    tmp[*it] = min(lastCount, value + 1);
                }
            }
            swap(dp, tmp);
        }
        
        if (dp.empty()) return -1;

        int res{INT_MAX};
        for (const auto& [_, value]: dp)
            res = min(res, value);

        return res;
    }
};

Time complexity is O(arr1 length * arr2 length)

Space complexity is O(max(arr1 length, arr2 length))