[Leetcode]1574. Shortest Subarray to be Removed to Make Array Sorted

Given an integer array arr, remove a subarray (can be empty) from arr such that the remaining elements in arr are non-decreasing.
A subarray is a contiguous subsequence of the array.
Return the 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

Subscribe
Notify of