educative.io

Educative

Improvements on my approach?

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