Learning On the Way

581. Shortest Unsorted Continuous Subarray

Given an integer array nums, you need to find one continuous subarray such that if you only sort this subarray in non-decreasing order, then the whole array will be sorted in non-decreasing order.

Return the shortest such subarray and output its length.

def findUnsortedSubarray(self, nums: list[int]) -> int:
    max_so_far = nums[:]
    for i in range(1, len(nums)):
        max_so_far[i] = max(max_so_far[i - 1], nums[i])

    min_so_far = nums[:]
    for i in range(len(nums) - 2, -1, -1):
        min_so_far[i] = min(min_so_far[i + 1], nums[i])

    i = -1
    while i + 1 < len(nums) and max_so_far[i + 1] == min_so_far[i + 1]:
        i += 1

    j = len(nums)
    while j - 1 >= 0 and max_so_far[j - 1] == min_so_far[j - 1]:
        j -= 1

    return max(0, j - i - 1)