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 $-\infty$ and $\infty$ 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]=\infty$.
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 \in [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] \geq \infty$, it means that it cannot be converted into a strictly increasing array, return $-1$, otherwise return $f[n-1]$.
The time complexity is $(n \times (\log m + \min(m, n)))$, and the space complexity is $O(n)$. Here, $n$ is the length of $arr1$.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| 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]
|
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
43
44
| 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;
}
}
|
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
| 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];
}
};
|
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
| 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]
}
|
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
| 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];
}
|
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
43
44
45
46
| 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;
}
}
|
