[Python] Two Pointers Approach with Explanation
Since we can only remove a subarray, the final remaining elements must be either: (1) solely a prefix, (2) solely a suffix or (3) a merge of the prefix and suff
Since we can only remove a subarray, the final remaining elements must be either: (1) solely a prefix, (2) solely a suffix or (3) a merge of the prefix and suffix.\n1. Find the monotone non-decreasing prefix [a_0 <= ... a_i | ...]\n\t- `l` is the index such that `arr[l+1] < arr[l]`\n2. Find the monotone non-decreasing suffix [... | a_j <= ... a_n]\n\t- `r` is the index such that `arr[r-1] > arr[r]`\n3. Try to "merge 2 sorted arrays", if we can merge, update our minimum to remove.\n\n```\nclass Solution:\n    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n        l, r = 0, len(arr) - 1\n        while l < r and arr[l+1] >= arr[l]:\n            l += 1\n        if l == len(arr) - 1:\n            return 0 # whole array is sorted\n        while r > 0 and arr[r-1] <= arr[r]:\n            r -= 1\n        toRemove = min(len(arr) - l - 1, r) # case (1) and (2)\n\t\t\n\t\t# case (3): try to merge\n        for iL in range(l+1):\n            if arr[iL] <= arr[r]:\n                toRemove = min(toRemove, r - iL - 1)\n            elif r < len(arr) - 1:\n                r += 1\n            else:\n                break\n        return toRemove\n```
['Two Pointers']