-
Notifications
You must be signed in to change notification settings - Fork 0
LC 0581 [M] Shortest Unsorted Continuous Subarray
Code with Senpai edited this page Oct 7, 2020
·
1 revision
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
footer