Shortest Subarray to be Removed to Make Array Sorted

Shortest Subarray to be Removed to Make Array Sorted

 Given an integer array arr, remove a subarray (can be empty) from arr such that the remaining elements in arr are non-decreasing.

A subarray is a contiguous subsequence of the array.

Return the length of the shortest subarray to remove.

 

Example 1:

Input: arr = [1,2,3,10,4,2,3,5]
Output: 3
Explanation: The shortest subarray we can remove is [10,4,2] of length 3. The remaining elements after that will be [1,2,3,3,5] which are sorted.
Another correct solution is to remove the subarray [3,10,4].

Example 2:

Input: arr = [5,4,3,2,1]
Output: 4
Explanation: Since the array is strictly decreasing, we can only keep a single element. Therefore we need to remove a subarray of length 4, either [5,4,3,2] or [4,3,2,1].

Example 3:

Input: arr = [1,2,3]
Output: 0
Explanation: The array is already non-decreasing. We do not need to remove any elements.

Example 4:

Input: arr = [1]
Output: 0

 

Constraints:

• 1 <= arr.length <= 10^5
• 0 <= arr[i] <= 10^9

class Solution {

public:

    int findLengthOfShortestSubarray(vector<int>& arr) 

    {

        int n=arr.size(),ans=INT_MAX;

        int i=0;

        while(i<n-1&&arr[i]<=arr[i+1])

            ++i;

        ans=min(ans,n-i-1);

        // cout<<n-i-1<<" ";

        int j=n-1;

        while(j>0&&arr[j-1]<=arr[j])

            --j;

        // cout<<j<<" ";

        ans=min(ans,j);

        int tmp=i;

        i=0;

        stack<int> s,s1;

        while(i<j&&arr[i]<=arr[j])

        {

            if(s.empty()||(s.top()<=arr[i]))

            {

                s.push(arr[i]);

            ans=min(ans,j-i-1);

            // cout<<j-i-1<<" ";

            }else{

                break;

            }

            ++i;

        }

        

        j=n-1;

        i=tmp;

        

         while(i<j&&arr[i]<=arr[j])

        {

            if(s1.empty()||(s1.top()>=arr[j]))

            {

                s1.push(arr[j]);

            ans=min(ans,j-i-1);

            // cout<<j-i<<" ";

            }else{

                break;

            }

            --j;

        }

        // cout<<endl;

        return ans;

    }

};