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: Replace5
with2
, thenarr1 = [1, 2, 3, 6, 7]
.
Example 2:
Input: arr1 = [1,5,3,6,7], arr2 = [4,3,1] Output: 2 Explanation: Replace5
with3
and then replace3
with4
.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
Solution: DP
Time complexity: O(mn)
Space complexity: O(mn) -> O(m + n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
// Author: Huahua class Solution { public: int makeArrayIncreasing(vector<int>& a, vector<int>& c) { constexpr int kInf = 1e9; int m = a.size(); // Sort b and make it only containing unique numbers. sort(begin(c), end(c)); vector<int> b; for (int i = 0; i < c.size(); ++i) { if (!b.empty() && c[i] == b.back()) continue; b.push_back(c[i]); } int n = b.size(); // min steps to make a[0~i] valid by keeping a[i] vector<int> keep(m, kInf); keep[0] = 0; // swap[i][j] := min steps to make a[0~i] valid by a[i] = b[j] vector<int> swap(n, 1); for (int i = 1; i < m; ++i) { int min_keep = kInf; int min_swap = kInf; vector<int> temp(n, kInf); for (int j = 0; j < n; ++j) { if (j > 0) min_swap = min(min_swap, swap[j - 1] + 1); if (a[i] > b[j]) min_keep = min(min_keep, swap[j]); if (a[i] > a[i - 1]) keep[i] = keep[i - 1]; if (b[j] > a[i - 1]) temp[j] = keep[i - 1] + 1; temp[j] = min(temp[j], min_swap); keep[i] = min(keep[i], min_keep); } temp.swap(swap); } int s = *min_element(begin(swap), end(swap)); int k = keep.back(); int ans = min(s, k); return ans >= kInf ? -1 : ans; } }; |