🚀 Easy O(n) Solution | Beats 100% | Minimal Subarray Removal to Sort Array
Intuition\nThe solution identifies the shortest subarray to remove to make the array non-decreasing by dividing the array into three parts:\n\n1. Left and Right
# Intuition\nThe solution identifies the shortest subarray to remove to make the array non-decreasing by dividing the array into three parts:\n\n1. **Left and Right Sorted Parts:** First, it finds the longest non-decreasing sequences from the start (`left`) and end (`right`) of the array. If these sequences cover the entire array, no removal is needed.\n   \n2. **Minimize Removal:** For cases where removing elements is needed, the code tries to "bridge" the left and right parts to make the array non-decreasing, minimizing the elements removed by checking possible points to connect them.\n\nThe result is the smallest length of a subarray to remove for the array to become non-decreasing.\n\n# Approach\n1. Identify Boundaries: Find the longest non-decreasing subarrays from the start (left) and end (right). If they meet, the array is already sorted, so return 0.\n\n2. Calculate Initial Removals: Assume removing all elements after left or before right and take the minimum of these two options.\n\n3. Bridge Left and Right Parts: Use two pointers to try merging elements from the left and right parts to form a continuous non-decreasing array, updating the minimum elements to remove as you go.\n\n4. Return Result: The minimum calculated removals gives the answer.\n\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(1)\n\n# Code\n```cpp []\n\nclass Solution {\npublic:\n    int findLengthOfShortestSubarray(vector<int>& arr) {\n        int n = arr.size();\n        int left = 0, right = n - 1;\n\n        while (left + 1 < n && arr[left] <= arr[left + 1]) {\n            left++;\n        }\n        if (left == n - 1) return 0;\n\n        while (right > 0 && arr[right - 1] <= arr[right]) {\n            right--;\n        }\n\n        int ans = min(n - left - 1, right);\n\n        int i = 0, j = right;\n        while (i <= left && j < n) {\n            if (arr[i] <= arr[j]) {\n                ans = min(ans, j - i - 1);\n                i++;\n            } else {\n                j++;\n            }\n        }\n        \n        return ans;\n    }\n};\n\n```
['Array', 'Two Pointers', 'Greedy', 'C++']