581. Shortest Unsorted Continuous Subarray

class Solution:
    def findUnsortedSubarray(self, A: List[int]) -> int:
        """
        main idea: keep extending worst case in left bound and right bound, compare with target array to get the first abnormal position 
                    1. create two cached array to record historical min,max point
                    2. left  -> right get the smaller value when adjacent two number is not ascending;
                    3. right -> left get bigger number when two adjacent numbers is not descending
                    4. loop through original array, compare is current number is not same as left cached 
                    5. reverse loop original array, record first number that's not sorted position compare with right cache  
        tc O(N) sc O(N)
        """
        n = len(A)
        minv,maxv = float('inf'),float('-inf')
        lmax , rmin = [0]*n,[0]*n 
        for i in range(n):
            maxv = max(A[i],maxv) # maxv keep global max value so far to make sure lmax is non-decending
            lmax[i] = maxv
        for j in range(n-1,-1,-1):
            minv = min(A[j],minv)  # keep rmin non-ascending in reverse => non-decending in order 
            rmin[j] = minv
        
       # rmin = rmin[::-1]
       # print(rmin,lmax)
        l,r = 0, n-1
        
        while l < n and A[l] <= rmin[l]: # find the first position bigger than expected 
            l += 1 
        
        while r > l and A[r] >= lmax[r]: # in reverse order, find the first position smaller than expected !!! note here r < l to avoid overlapping 
            r -= 1
        return r-l + 1 

class Solution:
    def findUnsortedSubarray(self, A: List[int]) -> int:
        """
        tc O(N) sc O(1)
        """
        n = len(A)
        l,r = -1,-2 # for cases when A is sorted in the beginning 
        minv,maxv = float('inf'),float('-inf')
        for i in range(n):
            maxv = max(maxv,A[i])
            minv = min(minv,A[n-1-i])
            if A[i] < maxv:# find the last abnormal 
                r = i
            if A[n-1-i] > minv: # find the first abnormal 
                l = n-1 -i 
        return r-l +1