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