Given an integer array
arr, remove a subarray (can be empty) from
arrsuch that the remaining elements in
arrare 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:
l<=r. Therefore our strategy could be:
- Find the longest non-decreasing subarrays
l<=rstarting from the front and back accordingly.
- Then the longest remaining non-decreasing must be some combination of
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