Given an integer array`arr`

, remove a subarray (can be empty) from`arr`

such that the remaining elements in`arr`

arenon-decreasing. A subarray is a contiguous subsequence of the array. Returnthe length of the shortest subarray to remove.

#### Two pointers 1

Noticing that we can only remove one subarray, therefore the remaining non-decreasing array is consist of two parts: `arr[0...l]`

and `arr[r...n]`

where `l<=r`

. Therefore our strategy could be:

- Find the longest non-decreasing subarrays
`arr[0...l]`

and`arr[r...n]`

where`l<=r`

starting from the front and back accordingly. - Then the longest remaining non-decreasing must be some combination of
`arr[0...i,j...n]`

where`i<l`

and`j>r`

. Here we can use two pointers.

The fact is, with the two non-decreasing subarrays, we don’t know how to combine them before-head. But we can approach this problem in a greedy manner – for each number of the subarray on the righthand side, we can find the longest subarray on the lefthand side such that they could be formed to one non-decreasing array. Two pointers would work.

```
class Solution:
def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
n = len(arr)
l,r = 0,n-1
while l < r and arr[l]<=arr[l+1]:
l += 1
while l < r and arr[r-1]<=arr[r]:
r -= 1
if l == r:
return 0
# print(l,r)
ret = min(n-l-1,r)
i,j = 0,r
while i <= l and j < n:
if arr[i] <= arr[j]:
ret = min(ret,j-i-1)
i += 1
else:
j += 1
return ret
```

#### Two pointers 2 – optimised

Inspired by @lee215, we can further optimize the previous approach a little bit – we don’t actually need to find the left non-decreasing subarray. We could only find the right non-decreasing subarray and then start iterating from the beginning.

```
class Solution:
def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
n = len(arr)
l,r = 0,n-1
while l < r and r>0 and arr[r-1]<=arr[r]:
r -= 1
if r == 0:
return 0
ret = r
for l in range(n):
if l > 0 and arr[l-1]>arr[l]:
break
while r < n and arr[l] > arr[r]:
r += 1
ret = min(ret,r-l-1)
return ret
```