[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