Python | Two Pointers & Prefix/Suffix Analysis
see the Successfully Accepted Submission\n\n# Code\npython3 []\nclass Solution:\n    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n        n =
[see the Successfully Accepted Submission](https://leetcode.com/problems/shortest-subarray-to-be-removed-to-make-array-sorted/submissions/1453067650/?envType=daily-question&envId=2024-11-15)\n\n# Code\n```python3 []\nclass Solution:\n    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n        n = len(arr)\n        \n        # Step 1: Find the longest non-decreasing prefix\n        left = 0\n        while left + 1 < n and arr[left] <= arr[left + 1]:\n            left += 1\n        \n        # If the entire array is non-decreasing\n        if left == n - 1:\n            return 0\n        \n        # Step 2: Find the longest non-decreasing suffix\n        right = n - 1\n        while right > 0 and arr[right - 1] <= arr[right]:\n            right -= 1\n        \n        # Step 3: The minimum elements to remove is the minimum of:\n        # 1. Removing all elements from right of \'left\' or left of \'right\'\n        result = min(n - left - 1, right)\n        \n        # Step 4: Try to merge the prefix and suffix by checking if we can connect arr[left] and arr[right]\n        i, j = 0, right\n        while i <= left and j < n:\n            if arr[i] <= arr[j]:\n                result = min(result, j - i - 1)\n                i += 1\n            else:\n                j += 1\n        \n        return result\n\n```\n# Solution Approach\n\n## Edge Cases\n- If the array is already non-decreasing, return `0` since no removal is necessary.\n- If the array is strictly decreasing, we would need to remove all but one element.\n\n## Key Insight\nFind the longest non-decreasing prefix and the longest non-decreasing suffix of `arr`. This helps us establish portions of the array that are already sorted, reducing the problem to finding minimal overlap between these sorted parts.\n\n## Steps to Implement\n1. Traverse from the beginning to find the length of the longest non-decreasing prefix.\n2. Traverse from the end to find the length of the longest non-decreasing suffix.\n3. If the entire array is already sorted with the prefix and suffix covering the whole array, return `0`.\n4. Otherwise, explore two main possibilities:\n   - **Remove a middle subarray**: Merge prefix and suffix by checking all possible split points to see where they can be connected to maintain order.\n   - **Remove the shortest subarray between them**: Compute the minimal elements to remove to maintain a non-decreasing order.\n\n\n# Explanation of the Code\n\n## Identify Non-Decreasing Prefix and Suffix\n- We iterate to find the longest non-decreasing sequence from the start (`left`) and from the end (`right`).\n- If the array is entirely non-decreasing, we return `0` immediately.\n\n## Calculate Initial Result\n- We compute the minimum elements to remove by checking the remaining parts after `left` and before `right`.\n\n## Try to Merge Left and Right\n- We use two pointers (`i` and `j`) to see if any point in the prefix can align with the start of the suffix to form a non-decreasing array. \n- We adjust `result` to the minimal length of subarray removed whenever possible.\n\n# Complexity Analysis\n\n- **Time Complexity**: \\(O(n)\\), where \\(n\\) is the length of the array. This is achieved because we only make linear passes over the array.\n- **Space Complexity**: \\(O(1)\\), since we are only using a few extra variables.\n\n\n\n![image](https://assets.leetcode.com/users/images/b1e4af48-4da1-486c-bc97-b11ae02febd0_1696186577.992237.jpeg)
['Python3']