Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1187.html
1187. Make Array Strictly Increasing (Hard)
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
Related Topics:
Dynamic Programming
Solution 1. DP Top-down
// OJ: https://leetcode.com/problems/make-array-strictly-increasing/
// Time: O(MN * logN)
// Space: O(MN)
// Ref: https://leetcode.com/problems/make-array-strictly-increasing/discuss/379095/C%2B%2B-DFS-%2B-Memo
class Solution {
int dp[2001][2001] = {};
int dfs(vector<int>& A, vector<int>& B, int i, int prev) {
if (i >= A.size()) return 1;
int j = upper_bound(B.begin(), B.end(), prev) - B.begin();
if (dp[i][j]) return dp[i][j];
int skip = prev < A[i] ? dfs(A, B, i + 1, A[i]) : B.size() + 1;
int swap = j < B.size() ? 1 + dfs(A, B, i + 1, B[j]) : B.size() + 1;
return dp[i][j] = min(skip, swap);
}
public:
int makeArrayIncreasing(vector<int>& A, vector<int>& B) {
sort(B.begin(), B.end());
auto ans = dfs(A, B, 0, INT_MIN);
return ans > B.size() ? -1 : ans - 1;
}
};
Or pass the previous j
value into dfs
so that j
only traverse B
in one pass.
// OJ: https://leetcode.com/problems/make-array-strictly-increasing/
// Time: O(MN)
// Space: O(MN)
// Ref: https://leetcode.com/problems/make-array-strictly-increasing/discuss/379095/C%2B%2B-DFS-%2B-Memo
class Solution {
int dp[2001][2001] = {};
int dfs(vector<int>& A, vector<int>& B, int i, int j, int prev) {
if (i >= A.size()) return 1;
j = upper_bound(B.begin() + j, B.end(), prev) - B.begin();
if (dp[i][j]) return dp[i][j];
int skip = prev < A[i] ? dfs(A, B, i + 1, j, A[i]) : B.size() + 1;
int swap = j < B.size() ? 1 + dfs(A, B, i + 1, j, B[j]) : B.size() + 1;
return dp[i][j] = min(skip, swap);
}
public:
int makeArrayIncreasing(vector<int>& A, vector<int>& B) {
sort(B.begin(), B.end());
auto ans = dfs(A, B, 0, 0, INT_MIN);
return ans > B.size() ? -1 : ans - 1;
}
};
Solution 2. DP
// OJ: https://leetcode.com/problems/make-array-strictly-increasing/
// Time: O(MN * logN)
// Space: O(MN)
// Ref: https://leetcode.com/problems/make-array-strictly-increasing/discuss/377403/Python-DP-solution-with-explanation.
class Solution {
public:
int makeArrayIncreasing(vector<int>& A, vector<int>& B) {
int M = A.size(), N = B.size();
sort(B.begin(), B.end());
unordered_map<int, int> dp;
dp[-1] = 0;
for (int a : A) {
unordered_map<int, int> tmp;
for (auto &p : dp) {
if (a > p.first) {
int cnt = tmp.count(a) ? tmp[a] : INT_MAX;
tmp[a] = min(cnt, p.second);
}
int b = upper_bound(B.begin(), B.end(), p.first) - B.begin();
if (b < N) {
int cnt = tmp.count(B[b]) ? tmp[B[b]] : INT_MAX;
tmp[B[b]] = min(cnt, p.second + 1);
}
}
dp = tmp;
}
if (dp.empty()) return -1;
int ans = INT_MAX;
for (auto &p : dp) ans = min(ans, p.second);
return ans;
}
};
-
class Solution { public int makeArrayIncreasing(int[] arr1, int[] arr2) { TreeSet<Integer> set = new TreeSet<Integer>(); for (int num : arr2) set.add(num); int length = arr1.length; int[][] dp = new int[length][length + 1]; for (int i = 0; i < length; i++) { for (int j = 0; j <= length; j++) dp[i][j] = Integer.MAX_VALUE; } dp[0][0] = arr1[0]; dp[0][1] = set.first(); for (int i = 1; i < length; i++) { if (arr1[i] > dp[i - 1][0]) dp[i][0] = arr1[i]; for (int j = 1; j <= i; j++) { Integer nextNum = set.higher(dp[i - 1][j - 1]); if (nextNum != null) dp[i][j] = nextNum; if (arr1[i] > dp[i - 1][j]) dp[i][j] = Math.min(dp[i][j], arr1[i]); } Integer nextNum = set.higher(dp[i - 1][i]); if (nextNum != null) dp[i][i + 1] = nextNum; } for (int i = 0; i <= length; i++) { if (dp[length - 1][i] != Integer.MAX_VALUE) return i; } return -1; } }
-
// OJ: https://leetcode.com/problems/make-array-strictly-increasing/ // Time: O(MN * logN) // Space: O(MN) // Ref: https://leetcode.com/problems/make-array-strictly-increasing/discuss/379095/C%2B%2B-DFS-%2B-Memo class Solution { int dp[2001][2001] = {}; int dfs(vector<int>& A, vector<int>& B, int i, int prev) { if (i >= A.size()) return 1; int j = upper_bound(B.begin(), B.end(), prev) - B.begin(); if (dp[i][j]) return dp[i][j]; int skip = prev < A[i] ? dfs(A, B, i + 1, A[i]) : B.size() + 1; int swap = j < B.size() ? 1 + dfs(A, B, i + 1, B[j]) : B.size() + 1; return dp[i][j] = min(skip, swap); } public: int makeArrayIncreasing(vector<int>& A, vector<int>& B) { sort(B.begin(), B.end()); auto ans = dfs(A, B, 0, INT_MIN); return ans > B.size() ? -1 : ans - 1; } };
-
print("Todo!")