Stack
Array
Two Pointers
Binary Search
Monotonic Stack
Description
Given an integer array arr
, remove a subarray (can be empty) from arr
such that the remaining elements in arr
are non-decreasing .
Return the length of the shortest subarray to remove .
A subarray is a contiguous subsequence of the array.
Example 1:
Input: arr = [1,2,3,10,4,2,3,5]
Output: 3
Explanation: The shortest subarray we can remove is [10,4,2] of length 3. The remaining elements after that will be [1,2,3,3,5] which are sorted.
Another correct solution is to remove the subarray [3,10,4].
Example 2:
Input: arr = [5,4,3,2,1]
Output: 4
Explanation: Since the array is strictly decreasing, we can only keep a single element. Therefore we need to remove a subarray of length 4, either [5,4,3,2] or [4,3,2,1].
Example 3:
Input: arr = [1,2,3]
Output: 0
Explanation: The array is already non-decreasing. We do not need to remove any elements.
Constraints:
1 <= arr.length <= 105
0 <= arr[i] <= 109
Solutions
Solution 1
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 class Solution :
def findLengthOfShortestSubarray ( self , arr : List [ int ]) -> int :
n = len ( arr )
i , j = 0 , n - 1
while i + 1 < n and arr [ i ] <= arr [ i + 1 ]:
i += 1
while j - 1 >= 0 and arr [ j - 1 ] <= arr [ j ]:
j -= 1
if i >= j :
return 0
ans = min ( n - i - 1 , j )
for l in range ( i + 1 ):
r = bisect_left ( arr , arr [ l ], lo = j )
ans = min ( ans , r - l - 1 )
return ans
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 class Solution {
public int findLengthOfShortestSubarray ( int [] arr ) {
int n = arr . length ;
int i = 0 , j = n - 1 ;
while ( i + 1 < n && arr [ i ] <= arr [ i + 1 ] ) {
++ i ;
}
while ( j - 1 >= 0 && arr [ j - 1 ] <= arr [ j ] ) {
-- j ;
}
if ( i >= j ) {
return 0 ;
}
int ans = Math . min ( n - i - 1 , j );
for ( int l = 0 ; l <= i ; ++ l ) {
int r = search ( arr , arr [ l ] , j );
ans = Math . min ( ans , r - l - 1 );
}
return ans ;
}
private int search ( int [] arr , int x , int left ) {
int right = arr . length ;
while ( left < right ) {
int mid = ( left + right ) >> 1 ;
if ( arr [ mid ] >= x ) {
right = mid ;
} else {
left = mid + 1 ;
}
}
return left ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 class Solution {
public :
int findLengthOfShortestSubarray ( vector < int >& arr ) {
int n = arr . size ();
int i = 0 , j = n - 1 ;
while ( i + 1 < n && arr [ i ] <= arr [ i + 1 ]) {
++ i ;
}
while ( j - 1 >= 0 && arr [ j - 1 ] <= arr [ j ]) {
-- j ;
}
if ( i >= j ) {
return 0 ;
}
int ans = min ( n - 1 - i , j );
for ( int l = 0 ; l <= i ; ++ l ) {
int r = lower_bound ( arr . begin () + j , arr . end (), arr [ l ]) - arr . begin ();
ans = min ( ans , r - l - 1 );
}
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 func findLengthOfShortestSubarray ( arr [] int ) int {
n := len ( arr )
i , j := 0 , n - 1
for i + 1 < n && arr [ i ] <= arr [ i + 1 ] {
i ++
}
for j - 1 >= 0 && arr [ j - 1 ] <= arr [ j ] {
j --
}
if i >= j {
return 0
}
ans := min ( n - i - 1 , j )
for l := 0 ; l <= i ; l ++ {
r := j + sort . SearchInts ( arr [ j :], arr [ l ])
ans = min ( ans , r - l - 1 )
}
return ans
}
Solution 2
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 class Solution :
def findLengthOfShortestSubarray ( self , arr : List [ int ]) -> int :
n = len ( arr )
i , j = 0 , n - 1
while i + 1 < n and arr [ i ] <= arr [ i + 1 ]:
i += 1
while j - 1 >= 0 and arr [ j - 1 ] <= arr [ j ]:
j -= 1
if i >= j :
return 0
ans = min ( n - i - 1 , j )
r = j
for l in range ( i + 1 ):
while r < n and arr [ r ] < arr [ l ]:
r += 1
ans = min ( ans , r - l - 1 )
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 class Solution {
public int findLengthOfShortestSubarray ( int [] arr ) {
int n = arr . length ;
int i = 0 , j = n - 1 ;
while ( i + 1 < n && arr [ i ] <= arr [ i + 1 ] ) {
++ i ;
}
while ( j - 1 >= 0 && arr [ j - 1 ] <= arr [ j ] ) {
-- j ;
}
if ( i >= j ) {
return 0 ;
}
int ans = Math . min ( n - i - 1 , j );
for ( int l = 0 , r = j ; l <= i ; ++ l ) {
while ( r < n && arr [ r ] < arr [ l ] ) {
++ r ;
}
ans = Math . min ( ans , r - l - 1 );
}
return ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 class Solution {
public :
int findLengthOfShortestSubarray ( vector < int >& arr ) {
int n = arr . size ();
int i = 0 , j = n - 1 ;
while ( i + 1 < n && arr [ i ] <= arr [ i + 1 ]) {
++ i ;
}
while ( j - 1 >= 0 && arr [ j - 1 ] <= arr [ j ]) {
-- j ;
}
if ( i >= j ) {
return 0 ;
}
int ans = min ( n - 1 - i , j );
for ( int l = 0 , r = j ; l <= i ; ++ l ) {
while ( r < n && arr [ r ] < arr [ l ]) {
++ r ;
}
ans = min ( ans , r - l - 1 );
}
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 func findLengthOfShortestSubarray ( arr [] int ) int {
n := len ( arr )
i , j := 0 , n - 1
for i + 1 < n && arr [ i ] <= arr [ i + 1 ] {
i ++
}
for j - 1 >= 0 && arr [ j - 1 ] <= arr [ j ] {
j --
}
if i >= j {
return 0
}
ans := min ( n - i - 1 , j )
r := j
for l := 0 ; l <= i ; l ++ {
for r < n && arr [ r ] < arr [ l ] {
r += 1
}
ans = min ( ans , r - l - 1 )
}
return ans
}
GitHub