1574. Shortest Subarray to be Removed to Make Array Sorted

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        """ tc O(N) sc O(1)
        main idea: since we can  remove only one subarray to make whole array sorted,  we eigher remove (1) left sorted subarray's right side (2) right sorted subarray's left side (3) combined sorted left, right subarray after adjusting left, right pointers.
        1. find left sorted subarray  max length  and check corner case if left subarray reached the end 
        2. find right sorted subarray  max length, get possible min length to be removed 
        3. adjust one pointer(from the beginning) and keep updating valid smaller to_remove window size; 
        if A[r] < A[l], can move right ptr to tail one step until end, otherwise break 
        """
        l,r,n = 0,len(arr)-1,len(arr)
        while l < n-1 and arr[l] <= arr[l+1]:
            l += 1 
        if l == n-1: return 0
        while r > 0 and arr[r-1] <= arr[r]:
            r -= 1 
        to_remove = min(n-l-1, r)
        
        for left in range(l+1):
            if arr[left] <= arr[r]:
                to_remove = min(to_remove,r-left-1)
            elif r < n-1: # note boundary is n-1 not n 
                r += 1 
            else:
                break
        return to_remove

class Solution:
    def findLengthOfShortestSubarray(self, A: List[int]) -> int:
        """
        1. right -> left, find first point not decreasing 
        2. left start from 0 to r, keep until subarray ending with left is not non-decreasing 
        3. within left pointer's while loop, check if A[l] <=A[r], otherwise, right += 1
        4. each time left move one step, update min distance to be removed
        * note the edge cases (all increasing, all decreasing ) and left pointer's termination condition at last loop
        tc O(N) sc O(1)
        """
        
        n = len(A)
        l,r = 0,n-1

        for i in range(n-1,0,-1):
            if A[i] < A[i-1]:
                r = i
                break
        res = r
        while l < r and (l == 0 or A[l-1]<=A[l]):
            while r < n and A[r] < A[l]:
                r += 1
            res = min(res,r-l-1)
            l += 1 

        return res