Beats 100% || C++ || Two Pointers
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem requires finding the shortest subarray that needs to be removed from the gi
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem requires finding the shortest subarray that needs to be removed from the given array so that the entire array becomes non-decreasing. A clear approach would involve checking the already non-decreasing sections from both the start and end of the array and then minimizing the elements removed.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1.\tFirst, we identify the largest non-decreasing subarray from the end of the given array. We do this by iterating backward and finding the first index j where the order breaks.\n2.\tNext, we initialize ans as j, representing the initial assumption that we might have to remove the entire prefix up to j.\n3.\tWe then iterate from the beginning to find a non-decreasing subarray from the start and try to merge it with the non-decreasing subarray from the end. We check if the element at i from the start can be combined with the subarray starting from j.\n4.\tIf arr[i] is greater than arr[j], it implies that we cannot merge them, so we increment j to try merging with a greater value. At each valid merging point, we update ans to minimize the number of elements removed: ans = min(ans, j - i - 1).\n5.\tWe continue until we have checked all possible prefixes.\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int findLengthOfShortestSubarray(vector<int>& arr) {\n        int n = arr.size(), j=n-1;\n        while(j > 0 && arr[j] >= arr[j-1]){\n            j--;\n        }\n\n        int ans = j, i = 0;\n        while(i < j && (i == 0 || arr[i-1] <= arr[i])){\n            while(j < n && arr[i] > arr[j]){\n                j++;\n            }\n            ans = min(ans, j-i-1);\n            i++;\n        }\n        return ans;\n    }\n};\n```
['Array', 'Two Pointers', 'C++']