Description
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 <= 20000 <= arr1[i], arr2[i] <= 10^9
Solutions
Solution 1: Dynamic Programming
We define f[i] as the minimum number of operations to convert arr1[0,..,i] into a strictly increasing array, and arr1[i] is not replaced. Therefore, we set two sentinels -∞ and ∞ at the beginning and end of arr1. The last number is definitely not replaced, so f[n-1] is the answer. We initialize f[0]=0, and the rest f[i]=∞.
Next, we sort the array arr2 and remove duplicates for easy binary search.
For i=1,..,n-1, we consider whether arr1[i-1] is replaced. If arr1[i-1] \lt arr1[i], then f[i] can be transferred from f[i-1], that is, f[i] = f[i-1]. Then, we consider the case where arr[i-1] is replaced. Obviously, arr[i-1] should be replaced with a number as large as possible and less than arr[i]. We perform a binary search in the array arr2 and find the first index j that is greater than or equal to arr[i]. Then we enumerate the number of replacements in the range k ∈ [1, min(i-1, j)]. If arr[i-k-1] \lt arr2[j-k], then f[i] can be transferred from f[i-k-1], that is, f[i] = min(f[i], f[i-k-1] + k).
Finally, if f[n-1] ≥ ∞, it means that it cannot be converted into a strictly increasing array, return -1, otherwise return f[n-1].
The time complexity is (n × (log m + min(m, n))), and the space complexity is O(n). Here, n is the length of arr1.
PythonJavaC++GoTypeScriptC#
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](code-box)
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;
}
}(code-box)
class Solution {
public:
int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
sort(arr2.begin(), arr2.end());
arr2.erase(unique(arr2.begin(), arr2.end()), arr2.end());
const int inf = 1 << 30;
arr1.insert(arr1.begin(), -inf);
arr1.push_back(inf);
int n = arr1.size();
vector<int> f(n, inf);
f[0] = 0;
for (int i = 1; i < n; ++i) {
if (arr1[i - 1] < arr1[i]) {
f[i] = f[i - 1];
}
int j = lower_bound(arr2.begin(), arr2.end(), arr1[i]) - arr2.begin();
for (int 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);
}
}
}
return f[n - 1] >= inf ? -1 : f[n - 1];
}
};(code-box)
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]
}(code-box)
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];
}(code-box)
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;
}
}(code-box)
