Problem Description

Given an integer array arr, your task is to find the length of the shortest subarray that can be removed so that the remaining elements of arr are in non-decreasing order. In other words, after you remove a contiguous subarray (possibly empty), the rest of the array should be sorted in ascending order (with duplicates allowed).

• You must remove exactly one contiguous subarray (possibly of length 0, i.e., remove nothing).
• You cannot rearrange or reuse elements; only remove a single contiguous segment.
• Return the minimal possible length of the subarray to remove.

Example:
Input: arr = [1,2,3,10,4,2,3,5]
Output: 3
Explanation: Remove the subarray [10,4,2] to get [1,2,3,3,5] which is non-decreasing.

Thought Process

The naive approach might be to consider every possible subarray and check if removing it makes the array sorted. However, this is too slow for large arrays. Instead, let's rethink the problem:

• We want to keep as much of the original array as possible. That means we want to find the largest prefix and suffix that are already sorted.
• By removing the minimal subarray in between, we can potentially join the sorted prefix and suffix into one sorted array.
• We should also consider the cases where removing from the start or end gives us a sorted array (i.e., the prefix or suffix is already sorted).
• Optimizing the solution means not checking all O(n^2) subarrays, but instead leveraging these sorted regions.

Solution Approach

Here's how we can efficiently solve the problem step-by-step:

1. Find the Longest Non-Decreasing Prefix:
   Start from the left of the array and move right as long as each element is less than or equal to the next. Let left be the last index of this prefix.
2. Find the Longest Non-Decreasing Suffix:
   Start from the right of the array and move left as long as each element is greater than or equal to the previous. Let right be the first index of this suffix.
3. Edge Case:
   If the entire array is already sorted, return 0.
4. Initialize Answer:
   The minimal length to remove could be everything between the prefix and suffix: right - left - 1.
5. Try Merging Prefix and Suffix:
   For each index i in the prefix (from 0 to left), use binary search to find the smallest index j in the suffix (from right to end) such that arr[i] ≤ arr[j]. The subarray to remove is from i+1 to j-1.
6. Update the Minimum:
   Track the smallest length found during this process.

We use binary search for efficiency, as the suffix is sorted.

Example Walkthrough

Let's use the sample input arr = [1,2,3,10,4,2,3,5]:

• Find Prefix: [1,2,3,10] is non-decreasing (indices 0-3).
• Find Suffix: [2,3,5] is non-decreasing (indices 5-7).
• Possible Removals:
  • Remove from index 4 to 4: [4] (removes just 4). Remaining: [1,2,3,10,2,3,5] (not sorted).
  • Remove from index 4 to 5: [4,2]. Remaining: [1,2,3,10,3,5] (not sorted).
  • Remove from index 3 to 5: [10,4,2]. Remaining: [1,2,3,3,5] (sorted).
• Result: Removing 3 elements is the shortest way to make the array sorted.

Time and Space Complexity

• Brute-Force: For each possible subarray, check if removing it sorts the array. This is O(n³), since for each subarray you need to check order.
• Optimized Approach:
  • Finding the prefix and suffix: O(n)
  • For each prefix index, binary search on the suffix: O(n log n)
  • Overall: O(n log n) time, O(1) extra space (if we don't count input/output).

Summary

The key insight is that we don't need to check every possible subarray. By focusing on the longest sorted prefix and suffix, and efficiently merging them using binary search, we can quickly find the shortest subarray to remove. This approach is both elegant and efficient, leveraging properties of sorted arrays and search algorithms.

Code Implementation

class Solution:
    def findLengthOfShortestSubarray(self, arr):
        n = len(arr)
        left = 0
        while left + 1 < n and arr[left] <= arr[left + 1]:
            left += 1
        if left == n - 1:
            return 0
        right = n - 1
        while right > 0 and arr[right - 1] <= arr[right]:
            right -= 1
        res = min(n - left - 1, right)
        i = 0
        j = right
        while i <= left and j < n:
            if arr[i] <= arr[j]:
                res = min(res, j - i - 1)
                i += 1
            else:
                j += 1
        return res
      

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

class Solution {
    public int findLengthOfShortestSubarray(int[] arr) {
        int n = arr.length;
        int left = 0;
        while (left + 1 < n && arr[left] <= arr[left + 1]) left++;
        if (left == n - 1) return 0;
        int right = n - 1;
        while (right > 0 && arr[right - 1] <= arr[right]) right--;
        int res = Math.min(n - left - 1, right);
        int i = 0, j = right;
        while (i <= left && j < n) {
            if (arr[i] <= arr[j]) {
                res = Math.min(res, j - i - 1);
                i++;
            } else {
                j++;
            }
        }
        return res;
    }
}
      

var findLengthOfShortestSubarray = function(arr) {
    const n = arr.length;
    let left = 0;
    while (left + 1 < n && arr[left] <= arr[left + 1]) left++;
    if (left === n - 1) return 0;
    let right = n - 1;
    while (right > 0 && arr[right - 1] <= arr[right]) right--;
    let res = Math.min(n - left - 1, right);
    let i = 0, j = right;
    while (i <= left && j < n) {
        if (arr[i] <= arr[j]) {
            res = Math.min(res, j - i - 1);
            i++;
        } else {
            j++;
        }
    }
    return res;
};