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; } } ############ 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; } }