[Python3] Binary Search on answer with Sliding Window - Beats 100% of submissions
Approach\nWe approach this problem by identifying sorted segments at the beginning and end of the array, then using binary search to find the minimum number of 
# Approach\nWe approach this problem by identifying sorted segments at the beginning and end of the array, then using binary search to find the minimum number of elements to remove such that the resulting array becomes non-decreasing.\n\n1. **Find the sorted prefix and suffix**:  \n   - Calculate the longest non-decreasing prefix (`sorted_left`).\n   - Calculate the longest non-decreasing suffix (`sorted_right`).\n\n2. **Quick return for already sorted arrays**:  \n   If the entire array is sorted, return `0` as we do not need to delete any elements.\n\n3. **Binary search for the minimal number of removals**:  \n   - Use a helper function to check if a given number of total removals (split between the prefix and suffix) can result in a valid sorted array.\n   - Perform the binary search to find the smallest number of total removals.\n\n\n# Complexity\n- Time complexity:\n$$O(nlogn)$$ - We do a binary search where the check operation has a runtime complexity of $$O(n)$$\n- Space complexity:\n$$O(1)$$ - We don\'t use any extra space besides int variables\n\n# Code\n```python3 []\nclass Solution:\n    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n        n = len(arr)\n        sorted_left = 0\n        sorted_right = 0\n        prev = -inf\n        # Find the last index such that arr[0: index + 1] is sorted\n        for i in range(n):\n            if arr[i] >= prev:\n                sorted_left += 1\n            else:\n                break\n            prev = arr[i]\n        prev = inf\n        # Find the last index such that arr[index:n] is sorted\n        for i in range(n - 1, -1, -1):\n            if arr[i] <= prev:\n                sorted_right += 1\n            else:\n                break\n            prev = arr[i]\n\n        left_end = sorted_left - 1\n        right_start = n - sorted_right\n        # If the whole array is sorted we don\'t need to delete elements\n        if right_start == 0:\n            return 0\n\n        def check(val):\n            """\n            Check if we delete a total of val elements from the starting\n            and ending arrays combined whether we get a sorted array.\n            """\n            def check_valid(left_minus, right_plus):\n                """\n                Check if we remove `left_minus` and `right_plus` elements from each of the\n                arrays whether the resulting array is sorted. This check is O(1)\n                """\n                if left_end - left_minus == -1 or right_start + right_plus == n:\n                    return True\n                if left_end - left_minus < -1 or right_start + right_plus > n:\n                    return False\n\n                return arr[left_end - left_minus] <= arr[right_start + right_plus]\n\n            for i in range(val + 1):\n                if check_valid(i, val - i):\n                    return True\n\n            return False\n\n        l = 0\n        r = sorted_left + sorted_right - 1\n        # Binary search on the total elements we delete (Some can be deleted from the left subarray\n        # and some can be deleted from the right subarray)\n        while r > l:\n            mid = (r + l) // 2\n            if check(mid):\n                r = mid\n            else:\n                l = mid + 1\n\n        return l + right_start - left_end - 1\n```\n\n![image.png](https://assets.leetcode.com/users/images/9c35b298-94a9-46eb-b370-dcae685c6a6f_1731709592.9881878.png)\n
['Array', 'Binary Search', 'Sliding Window', 'Python3']