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: Replace5with2, thenarr1 = [1, 2, 3, 6, 7].
Example 2:
Input: arr1 = [1,5,3,6,7], arr2 = [4,3,1] Output: 2 Explanation: Replace5with3and then replace3with4.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 <= 20000 <= 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; } } ############ class Solution { public int makeArrayIncreasing(int[] arr1, int[] arr2) { Arrays.sort(arr2); int m = 0; for (int x : arr2) { if (m == 0 || x != arr2[m - 1]) { arr2[m++] = x; } } final int inf = 1 << 30; int[] arr = new int[arr1.length + 2]; arr[0] = -inf; arr[arr.length - 1] = inf; System.arraycopy(arr1, 0, arr, 1, arr1.length); int[] f = new int[arr.length]; Arrays.fill(f, inf); f[0] = 0; for (int i = 1; i < arr.length; ++i) { if (arr[i - 1] < arr[i]) { f[i] = f[i - 1]; } int j = search(arr2, arr[i], m); for (int k = 1; k <= Math.min(i - 1, j); ++k) { if (arr[i - k - 1] < arr2[j - k]) { f[i] = Math.min(f[i], f[i - k - 1] + k); } } } return f[arr.length - 1] >= inf ? -1 : f[arr.length - 1]; } private int search(int[] nums, int x, int n) { int l = 0, r = n; while (l < r) { int mid = (l + r) >> 1; if (nums[mid] >= x) { r = mid; } else { l = mid + 1; } } return l; } } -
// 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; } }; -
class Solution: def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int: arr2.sort() m = 0 for x in arr2: if m == 0 or x != arr2[m - 1]: arr2[m] = x m += 1 arr2 = arr2[:m] arr = [-inf] + arr1 + [inf] n = len(arr) f = [inf] * n f[0] = 0 for i in range(1, n): if arr[i - 1] < arr[i]: f[i] = f[i - 1] j = bisect_left(arr2, arr[i]) for k in range(1, min(i - 1, j) + 1): if arr[i - k - 1] < arr2[j - k]: f[i] = min(f[i], f[i - k - 1] + k) return -1 if f[n - 1] >= inf else f[n - 1] -
func makeArrayIncreasing(arr1 []int, arr2 []int) int { sort.Ints(arr2) m := 0 for _, x := range arr2 { if m == 0 || x != arr2[m-1] { arr2[m] = x m++ } } arr2 = arr2[:m] const inf = 1 << 30 arr1 = append([]int{-inf}, arr1...) arr1 = append(arr1, inf) n := len(arr1) f := make([]int, n) for i := range f { f[i] = inf } f[0] = 0 for i := 1; i < n; i++ { if arr1[i-1] < arr1[i] { f[i] = f[i-1] } j := sort.SearchInts(arr2, arr1[i]) for k := 1; k <= min(i-1, j); k++ { if arr1[i-k-1] < arr2[j-k] { f[i] = min(f[i], f[i-k-1]+k) } } } if f[n-1] >= inf { return -1 } return f[n-1] } func min(a, b int) int { if a < b { return a } return b } -
function makeArrayIncreasing(arr1: number[], arr2: number[]): number { arr2.sort((a, b) => a - b); let m = 0; for (const x of arr2) { if (m === 0 || x !== arr2[m - 1]) { arr2[m++] = x; } } arr2 = arr2.slice(0, m); const inf = 1 << 30; arr1 = [-inf, ...arr1, inf]; const n = arr1.length; const f: number[] = new Array(n).fill(inf); f[0] = 0; const search = (arr: number[], x: number): number => { let l = 0; let r = arr.length; while (l < r) { const mid = (l + r) >> 1; if (arr[mid] >= x) { r = mid; } else { l = mid + 1; } } return l; }; for (let i = 1; i < n; ++i) { if (arr1[i - 1] < arr1[i]) { f[i] = f[i - 1]; } const j = search(arr2, arr1[i]); for (let k = 1; k <= Math.min(i - 1, j); ++k) { if (arr1[i - k - 1] < arr2[j - k]) { f[i] = Math.min(f[i], f[i - k - 1] + k); } } } return f[n - 1] >= inf ? -1 : f[n - 1]; } -
public class Solution { public int MakeArrayIncreasing(int[] arr1, int[] arr2) { Array.Sort(arr2); int m = 0; foreach (int x in arr2) { if (m == 0 || x != arr2[m - 1]) { arr2[m++] = x; } } int inf = 1 << 30; int[] arr = new int[arr1.Length + 2]; arr[0] = -inf; arr[arr.Length - 1] = inf; for (int i = 0; i < arr1.Length; ++i) { arr[i + 1] = arr1[i]; } int[] f = new int[arr.Length]; Array.Fill(f, inf); f[0] = 0; for (int i = 1; i < arr.Length; ++i) { if (arr[i - 1] < arr[i]) { f[i] = f[i - 1]; } int j = search(arr2, arr[i], m); for (int k = 1; k <= Math.Min(i - 1, j); ++k) { if (arr[i - k - 1] < arr2[j - k]) { f[i] = Math.Min(f[i], f[i - k - 1] + k); } } } return f[arr.Length - 1] >= inf ? -1 : f[arr.Length - 1]; } private int search(int[] nums, int x, int n) { int l = 0, r = n; while (l < r) { int mid = (l + r) >> 1; if (nums[mid] >= x) { r = mid; } else { l = mid + 1; } } return l; } }