Here is my proposed solution… any suggestions? I am having tough time with the while condition (and the redundancy it has with the conditions inside) . Would like any improvement on that.
def shortest_window_sort(arr): minv, maxv = 1e32, -1e32 left, right = 0, len(arr)-1 left_freeze, right_freeze = False, False for e in arr: minv = min(e, minv) maxv = max(e, maxv) # check if ends of the arrays contain the min and the max # if not, then freeze and don't increment if arr[left] != minv: left_freeze = True if arr[right] != maxv: right_freeze = True # two pointer approach where we increment only of next element # is in the correct order. If not, we freeze while left < right and (not left_freeze or not right_freeze): # check the left side: if next element is greater or equal, then increment # otherwise (out of order), freeze. if arr[left+1] >= arr[left] and not left_freeze: left+=1 else: left_freeze = True # same as before if arr[right-1] <= arr[right] and not right_freeze: right-=1 else: right_freeze = True # if we have any freeze then return size of the window if lblocked or rblocked: return right - left + 1 else: return 0