Shortest Subarray To Be Removed To Make Array Sorted - C++ Solution
IntuitionApproachComplexity
Time complexity: O(n)

Space complexity: O(n)
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity: $O(n)$
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: $O(n)$
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
public:
    int findLengthOfShortestSubarray(vector<int>& arr) {
        vector<int> lstack {arr[0]};
        vector<int> rstack;

        for (int i = 1; i < arr.size(); i++) {
            if (arr[i] >= arr[i-1]) {
                lstack.push_back(arr[i]);
            } else {
                break;
            }
        }


        int max = lstack.size() + rstack.size();
        for (int i = arr.size() - 1; i >= lstack.size(); i--) {
            if (rstack.empty() or arr[i] <= rstack.back()) {
                rstack.push_back(arr[i]);
                while (not lstack.empty() and arr[i] < lstack.back())
                    lstack.pop_back();
            } else {
                break;
            }

            max = std::max((int)(lstack.size() + rstack.size()), max);
        }

        return arr.size() - max;
    }
};
```
['Monotonic Stack', 'C++']