LC 0581 [M] Shortest Unsorted Continuous Subarray - ALawliet/algorithms GitHub Wiki

class Solution:
    def findUnsortedSubarray(self, arr: List[int]) -> int:
        l, r = 0, len(arr) - 1
        
        # find first num out of sorting order from beginning 
        while l < len(arr) - 1 and arr[l] <= arr[l + 1]:
            l += 1
        
        # if already sorted
        if l == len(arr) - 1:
            return 0
        
        # find first number out of sorting order from the end
        while r > 0 and arr[r] >= arr[r - 1]:
            r -= 1
            
        # find the max and min of the subarray
        subarray_max = max(arr[l:r+1])
        subarray_min = min(arr[l:r+1])
            
        # extend subarray left to include any num which is bigger than the min of the subarray
        while l > 0 and arr[l - 1] > subarray_min:
            l -= 1
            
        # extend subarray right to include any num which is smaller than the max of the subarray
        while r < len(arr) - 1 and arr[r + 1] < subarray_max:
            r += 1
            
        return r - l + 1