Find prefix & suffix non-decreasing then 2 pointers vs  monotonic stack||beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \nFind the longest prefix & suffix non-descreasing subarrays. \nThen use 2-pointer method
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nFind the longest prefix & suffix non-descreasing subarrays. \nThen use 2-pointer method to find the min number of removing elements in the middle to form a non-descreasing subarray.\n\nSince monotonic stack is tagged by LC, the 2nd approach uses monotonic stack both in C++ & Python.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Let `left` denote the position for that  the longest prefix subarray ends. \n2. If `left==n-1`, an early stop with returning 0\n3. Let `right` denote the position for that  the longest suffix subarray starts. \n4. Initialize `min(n-left-1, right)`\n5. Use 2-pointer to find the min number of removing elements in the middle to form a non-descreasing subarray as follows\n```\nfor (int i = 0, j = right; i <= left && j < n; ) {\n    if (arr[i] <= arr[j]) {\n    //  remove elements  with index in (i, j)\n        remove = min(remove, j-i-1);\n        i++;\n    } \n    else j++;  \n}\n```\n6. `remove` is the answer\n7. Monotonic stack implementation is made which is a modification for the 2-pointer method.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(1)$$\nmonotonic stack: $O(n)$\n# Code||C++ 2 pointers\n```cpp []\nclass Solution {\npublic:\n    int findLengthOfShortestSubarray(vector<int>& arr) {\n        const int n = arr.size();\n        \n        // Find longest non-decreasing prefix\n        int left= 0;\n        for (; left+1 < n && arr[left] <= arr[left+1]; left++); \n        \n        // array is already non-decreasing\n        if (left== n-1) return 0;\n        \n        // Find longest non-decreasing suffix\n        int right = n-1;\n        for (; right>left && arr[right-1] <= arr[right]; right--);     \n        \n        // to remove as the smaller of removing all from either end\n        int remove = min(n-left-1, right);\n        \n        // Try to merge left and right parts\n        for (int i = 0, j = right; i <= left && j < n; ) {\n            if (arr[i] <= arr[j]) {\n                //  remove elements  with index in (i, j)\n                remove = min(remove, j-i-1);\n                i++;\n            } \n            else j++;  \n        }\n        \n        return remove;\n    }\n};\n\n```\n# using monotonic stack||C++ 0ms beats 100%\n```C++ []\nclass Solution {\npublic:\n    static int findLengthOfShortestSubarray(vector<int>& arr) {\n        int n = arr.size();\n        \n        // Find longest non-decreasing prefix\n        int left= 0;\n        for (; left+1 < n && arr[left] <= arr[left+1]; left++); \n        \n        // array is already non-decreasing\n        if (left== n-1) return 0;\n\n        // Monotonic stack for  non-descreasing suffix\n        vector<int> stack={n-1};\n        for (int r= n-2; r>left; r--) {\n            if (arr[r] <= arr[r+1])\n                stack.push_back(r);\n            else break;\n        }\n\n        // to remove as the smaller of removing all from either end\n        int remove= min(n-left-1, stack.back());\n\n        // Try to merge left and right parts\n        for (int i = 0; i <=left; i++) {\n            // find j=stack.back() s.t. arr[j]>= arr[i] \n            while (!stack.empty() && arr[i]>arr[stack.back()])\n                stack.pop_back();\n    \n            if (!stack.empty()) \n                remove = min(remove, stack.back()-i-1);\n        }\n\n        return remove;\n    }\n};\n\n\n\n```\n```Python []\nclass Solution:\n    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n        n, left=len(arr), 0\n        while left+1<n and arr[left]<=arr[left+1]: left+=1\n\n        if left==n-1: return 0\n\n        stack=[n-1]\n        for r in range(n-2, left, -1):\n            if arr[r]<=arr[r+1]: stack.append(r)\n            else: break\n        \n        remove=min(n-left-1, stack[-1])\n        for i in range(0, left+1):\n            while stack and arr[i]>arr[stack[-1]]: stack.pop()\n            if stack: remove=min(remove, stack[-1]-i-1)\n        return remove\n        \n```
['Array', 'Two Pointers', 'Monotonic Stack', 'C++', 'Python3']