Array
Binary Search
Dynamic Programming
Sorting
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 <= 2000
0 <= 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$.
Python3 Java C++ Go TypeScript C#
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 ;
}
}
GitHub