Shortest Subarray to be Removed to Make Array Sorted

Leetcode Problem:

• Shortest Subarray to be Removed to Make Array Sorted

Summary

• Given an integer array, remove a subarray such that the remaining elements are non-decreasing and return the length of the shortest subarray to remove.

Approach

• The approach used is to find the first decreasing pair in the array and then try to find the longest subarray that can be removed without breaking the non-decreasing sequence
• If the first element is greater than or equal to the last element, we can return the length of the subarray that can be removed from the beginning
• Otherwise, we need to try to find the longest subarray that can be removed from the end.

Complexity

• O(n) where n is the size of the array

Explanation

• The solution starts by finding the first decreasing pair in the array
• If no such pair is found, it means the array is already non-decreasing, so we return 0
• Otherwise, we find the longest subarray that can be removed without breaking the non-decreasing sequence
• We do this by trying to find the longest subarray that can be removed from the end of the array
• If the first element is greater than or equal to the last element, we can return the length of the subarray that can be removed from the beginning
• Otherwise, we need to try to find the longest subarray that can be removed from the end
• We use two pointers, left and right, to find the longest subarray that can be removed
• We start by trying to find the longest subarray that can be removed from the end of the array
• If the current element is greater than or equal to the previous element, we move the right pointer to the previous element
• If the current element is less than the previous element, we move the left pointer to the previous element
• We repeat this process until we find the longest subarray that can be removed without breaking the non-decreasing sequence
• We then return the length of the subarray that can be removed.

Solution Code:

class Solution {
public:
    int findLengthOfShortestSubarray(vector& arr) {
        int left;
        for(left = 0 ; left < arr.size() - 1; left++){
            if(arr[left] > arr[left+1]){
                break;
            }
        }
        if (left == arr.size() - 1) return 0;
        
        int right;
        for(right = arr.size() - 1; right > 0; right--){
            if(arr[right-1] > arr[right]){
                break;
            }
        }
        if (arr[left] <= arr[right]) return right - left -1;
        int t = arr.size() - left -1;
        int ans = min(t, right);
        int i = 0;
        while (i <= left && right < arr.size()){
            if (arr[i] <= arr[right]){
                ans = min(ans, right - i - 1);
            }

            if (i+1 <= left && arr[i+1] <= arr[right]){
                i++;
            } else{
                right++;
            }
        }
        return ans;
    }
};