Shortest Subarray To Be Removed To Make Array Sorted - Leetcode Solution

The problem "Shortest Subarray to be Removed to Make Array Sorted" on LeetCode can be solved efficiently using a two-pointer approach. The problem statement requires us to find the shortest continuous subarray of an unsorted array, which if removed, makes the remaining subarray sorted in ascending order.

Approach:

1. To solve this problem, we can start by finding the longest non-decreasing subarray from the left end of the array. We can do this by traversing the array from the left end and keeping track of the maximum value seen so far.

2. Next, we find the longest non-increasing subarray from the right end of the array. We can do this by traversing the array from the right end and keeping track of the minimum value seen so far.

3. We can take the intersection of these two subarrays to obtain the contiguous subarray which needs to be removed to make the array sorted.

4. Finally, we compute the length of this subarray and return it as the result.

Let's implement the above approach in the code.

Code:

class Solution {
public:
    int findLengthOfShortestSubarray(vector<int>& nums) {
        int n = nums.size();
        int left = 0, right = n-1;
        
        // Find the longest non-decreasing subarray from left end
        while (left+1 < n && nums[left] <= nums[left+1]) left++;
        
        // If the entire array is already sorted, return 0
        if (left == n-1) return 0;
        
        // Find the longest non-increasing subarray from right end
        while (right > 0 && nums[right-1] <= nums[right]) right--;
        
        // Compute the minimum length of the subarray to be removed
        int ans = min(n-1-left, right);
        
        // Merge left and right subarrays and find shortest subarray
        int i = 0, j = right;
        while (i <= left && j < n) {
            if (nums[i] <= nums[j]) {
                ans = min(ans, j-i-1);
                i++;
            }
            else {
                j++;
            }
        }
        return ans;
    }
};

Time Complexity: O(n), where n is the size of the input array. We traverse the array twice from left and right ends, and then merge the left and right subarrays in linear time.

Space Complexity: O(1), as we do not use any additional data structures.

1