# 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`

``````class Solution {
public:
int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
int n = arr1.size();
if (n == 1) return 0;
set<int> st(arr2.begin(), arr2.end());
vector<vector<int>> dp(n + 1, vector<int>(n + 1, INT_MAX));
dp[0][0] = INT_MIN;
for (int j = 1; j <= n; ++j) {
for (int i = 0; i <= j; ++i) {
if (arr1[j - 1] > dp[i][j - 1]) {
dp[i][j] = arr1[j - 1];
}
if (i > 0) {
auto it = st.upper_bound(dp[i - 1][j - 1]);
if (it != st.end()) dp[i][j] = min(dp[i][j], *it);
}
if (j == n && dp[i][j] != INT_MAX) return i;
}
}
return -1;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1187

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

https://leetcode.com/problems/make-array-strictly-increasing/discuss/377403/Python-DP-solution-with-explanation.

https://leetcode.com/problems/make-array-strictly-increasing/discuss/377680/Simple-Java-DP-Solution-%2B-TreeSet-with-Explanation-beats-100

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation