refer to : https://www.algoexpert.io/questions/Subarray%20Sort
Problem Statement
Analysis
Code
def subarraySort(array): minOutOfOrder = float("inf") maxOutOfOrder = float("-inf") for i in range(len(array)): num = array[i] if isOutOfOrder(i, num, array): minOutOfOrder = min(minOutOfOrder, num) maxOutOfOrder = max(maxOutOfOrder, num) if maxOutOfOrder == float("-inf"):# or if minOutOfOrder == float("inf"), which means line 6 never has been hit, no unsorted values return [-1,-1] #check the correct position for the smallest valur of all the out of order values, from left to right subarrayLeftIdx = 0 while minOutOfOrder >= array[subarrayLeftIdx]: subarrayLeftIdx += 1 #check the correct position for the greatest valur of all the out of order values, from right to left subarrayRightIdx = len(array) - 1 while maxOutOfOrder <= array[subarrayRightIdx]: subarrayRightIdx -= 1 return [subarrayLeftIdx, subarrayRightIdx] # compare the current value to its two adjcent values # the first value has no left value, the last one has no right value def isOutOfOrder(i, num, array): if i == 0: return num > array[i + 1] if i == len(array) - 1: return num < array[i - 1] return num > array[i + 1] or num < array[i - 1]