shortest subarray to remove to be removed to keep array sorted

XXX. Find Length of Shortest Subarray to Remove

Two-Pointer

Greedy

Problem Statement:

Given an array arr, find the length of the shortest subarray to remove such that the remaining array is sorted in non-decreasing order.

Algorithm:

The algorithm uses a two-pointer approach to determine the shortest subarray to remove:

1. Start by finding the first point right from the end of the array where the array stops being sorted in non-decreasing order.
2. Initialize the answer as the length of the subarray starting from right to the end.
3. Iterate from the left with a pointer left and check if the left side is sorted:
• While the element at left does not match the criteria, move right forward to find the next valid number.
• Update the shortest subarray length as right - left - 1.

Complexity:

Time Complexity: O(n), where n is the length of the array. Each element is processed at most twice.
Space Complexity: O(1), as no additional data structures are used.

Java Implementation:

class Solution {
    // 2 pointer solution actually isn't too bad
    public int findLengthOfShortestSubarray(int[] arr) {
        int right = arr.length - 1;
        // Step 1: Find the first point from the end where the array stops being sorted
        // Traverse from the end to identify the portion that is already sorted in non-decreasing order
        while (right > 0 && arr[right] >= arr[right - 1]) 
            right--;

        // Initialize the answer with the length of the subarray starting from 'right'
        // This is the portion of the array to the right that is unsorted
        int ans = right;

        int left = 0;
        // Step 2: Iterate from the left to find the shortest subarray to remove
        while (left < right && (left == 0 || arr[left - 1] <= arr[left])) {
            // Step 3: Find the next valid number after arr[left]
            // Move 'right' forward until we find a valid position where arr[left] <= arr[right]
            while (right < arr.length && arr[left] > arr[right]) 
                right++;

            // Step 4: Update the shortest length by calculating the removal length
            // The subarray between 'left' and 'right' is the one to remove
            ans = Math.min(ans, right - left - 1);

            // Move the left pointer forward to explore other possibilities
            left++;
        }

        // Step 5: Return the minimum length of the subarray to remove
        return ans;
    }
}