# Shortest Subarray to be Removed to Make Array Sorted
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/shortest-subarray-to-be-removed-to-make-array-sorted)
Canonical: https://scaleengineer.com/dsa/problems/shortest-subarray-to-be-removed-to-make-array-sorted
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Stack, Monotonic Stack
**Companies:** [DE Shaw](https://scaleengineer.com/companies/de-shaw), [razorpay](https://scaleengineer.com/companies/razorpay)
---
## Problem
Given an integer array `arr`, remove a subarray (can be empty) from `arr` such that the remaining elements in `arr` are **non-decreasing**.

Return _the length of the shortest subarray to remove_.

A **subarray** is a contiguous subsequence of the array.

**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.

**Constraints:**

* `1 <= arr.length <= 105`
* `0 <= arr[i] <= 109`

# Approaches
## Brute Force Enumeration
This approach involves trying every possible contiguous subarray for removal. For each potential subarray removal, we construct the remaining array and check if it is sorted in non-decreasing order. We keep track of the length of the shortest subarray that results in a sorted array.
**Time:** O(N^3), where N is the number of elements in the array. The two nested loops for `i` and `j` result in O(N^2) pairs. For each pair, creating and checking the temporary array takes O(N) time. · **Space:** O(N), where N is the number of elements in the array. This is because in each iteration, a temporary list of size up to N is created to check for sortedness.
**Pros:** Simple to understand and implement.; Correctly solves the problem for small inputs.
**Cons:** Extremely inefficient due to its cubic time complexity.; Will result in a 'Time Limit Exceeded' error on platforms like LeetCode for the given constraints.; Uses extra space proportional to the input size in each iteration.
### Explanation
The most straightforward way to solve the problem is to consider every single subarray that could be removed. We can define a subarray to be removed by its start and end indices. Let's say we remove the subarray `arr[i...j-1]`. The remaining parts of the array are the prefix `arr[0...i-1]` and the suffix `arr[j...n-1]`. We can form a new array by combining these two parts and then check if this new array is sorted. We do this for all possible `i` and `j` and keep track of the minimum length `j - i` that yields a sorted array.

```java
class Solution {
    public int findLengthOfShortestSubarray(int[] arr) {
        int n = arr.length;
        int minLength = n - 1;

        // i is the start of the removed subarray
        // j is the end of the removed subarray + 1
        for (int i = 0; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                java.util.List<Integer> temp = new java.util.ArrayList<>();
                for (int k = 0; k < i; k++) {
                    temp.add(arr[k]);
                }
                for (int k = j; k < n; k++) {
                    temp.add(arr[k]);
                }

                boolean isSorted = true;
                for (int k = 0; k < temp.size() - 1; k++) {
                    if (temp.get(k) > temp.get(k + 1)) {
                        isSorted = false;
                        break;
                    }
                }

                if (isSorted) {
                    minLength = Math.min(minLength, j - i);
                }
            }
        }
        return minLength;
    }
}
```
### Algorithm
- Initialize `minLength` to `n`, the maximum possible length to remove.
- Use a nested loop to iterate through all possible start indices `i` (from `0` to `n`) and end indices `j` (from `i` to `n`) of a subarray to be removed.
- For each pair `(i, j)`, the subarray `arr[i...j-1]` is considered for removal.
- Create a temporary list by concatenating the prefix `arr[0...i-1]` and the suffix `arr[j...n-1]`.
- Iterate through the temporary list to check if it is sorted in non-decreasing order.
- If the list is sorted, update `minLength` with the length of the removed subarray, which is `j - i`.
- After checking all possibilities, return `minLength`.

## Optimized Brute Force with Precomputation
This approach improves upon the pure brute force method. Instead of rebuilding and re-checking the remaining array in each iteration, we can determine if the remaining parts form a sorted sequence more efficiently. The key observation is that the remaining array is sorted if and only if the prefix part is sorted, the suffix part is sorted, and the last element of the prefix is less than or equal to the first element of the suffix.
**Time:** O(N^2). Precomputation takes O(N), but the nested loops for `i` and `j` dominate the runtime with O(N^2) iterations, each taking O(1) time. · **Space:** O(N) for the `prefixSorted` and `suffixSorted` boolean arrays.
**Pros:** Significantly faster than the O(N^3) brute-force approach.; The logic is a clear optimization of the naive solution.
**Cons:** The O(N^2) time complexity is still too slow for the given constraints.; Requires O(N) extra space for the precomputation arrays.
### Explanation
We can optimize the O(N^3) brute force by avoiding the O(N) check inside the loops. The check for whether the remaining array is sorted can be broken down into three conditions: the prefix part must be sorted, the suffix part must be sorted, and the connection between them must be valid. We can precompute the sorted status of all possible prefixes and suffixes in O(N) time and store them in boolean arrays. Then, inside the O(N^2) loops, we can perform the check in O(1) time using these precomputed values.

```java
class Solution {
    public int findLengthOfShortestSubarray(int[] arr) {
        int n = arr.length;
        if (n <= 1) {
            return 0;
        }

        boolean[] prefixSorted = new boolean[n];
        prefixSorted[0] = true;
        for (int k = 1; k < n; k++) {
            prefixSorted[k] = prefixSorted[k - 1] && (arr[k - 1] <= arr[k]);
        }

        boolean[] suffixSorted = new boolean[n];
        suffixSorted[n - 1] = true;
        for (int k = n - 2; k >= 0; k--) {
            suffixSorted[k] = suffixSorted[k + 1] && (arr[k] <= arr[k + 1]);
        }

        int minLength = n - 1;
        for (int i = 0; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                boolean isPrefixOk = (i == 0) || prefixSorted[i - 1];
                boolean isSuffixOk = (j == n) || suffixSorted[j];
                boolean isConnectionOk = (i == 0) || (j == n) || (arr[i - 1] <= arr[j]);

                if (isPrefixOk && isSuffixOk && isConnectionOk) {
                    minLength = Math.min(minLength, j - i);
                }
            }
        }
        return minLength;
    }
}
```
### Algorithm
- Precompute a boolean array `prefixSorted` where `prefixSorted[k]` is true if `arr[0...k]` is non-decreasing. This takes O(N) time.
- Precompute a boolean array `suffixSorted` where `suffixSorted[k]` is true if `arr[k...n-1]` is non-decreasing. This also takes O(N) time.
- Initialize `minLength` to `n`.
- Iterate through all possible start indices `i` (from `0` to `n`) and end indices `j` (from `i` to `n`) of the subarray to remove.
- For each `(i, j)`, check the validity in O(1) time:
  1. The prefix `arr[0...i-1]` is sorted (check `prefixSorted[i-1]`).
  2. The suffix `arr[j...n-1]` is sorted (check `suffixSorted[j]`).
  3. The last element of the prefix is less than or equal to the first element of the suffix (`arr[i-1] <= arr[j]`).
- Handle edge cases where the prefix or suffix is empty.
- If all conditions are met, update `minLength = min(minLength, j - i)`.
- Return `minLength`.

## Two Pointers Approach
This is the most efficient approach with linear time complexity. The core idea is that any valid remaining array must be formed by a non-decreasing prefix of the original array and a non-decreasing suffix of the original array. We first identify the longest such prefix and suffix. Then, we explore three possibilities for the shortest removal: removing everything after the prefix, removing everything before the suffix, or merging a part of the prefix with a part of the suffix.
**Time:** O(N). Finding `left` takes O(N), finding `right` takes O(N), and the two-pointer scan also takes O(N) because pointers `i` and `j` only move in one direction across the array. The total complexity is O(N) + O(N) + O(N) = O(N). · **Space:** O(1), as it only uses a few variables to store pointers and the minimum length, regardless of the input size.
**Pros:** Optimal time complexity of O(N).; Optimal space complexity of O(1).; Efficiently handles large inputs within time limits.
**Cons:** The logic is more complex and less intuitive than brute-force approaches.; Requires careful handling of pointers and edge cases.
### Explanation
A key insight is that the final sorted array will consist of a prefix `arr[0...i]` and a suffix `arr[j...n-1]` from the original array, where `arr[0...i]` and `arr[j...n-1]` are themselves non-decreasing, and `arr[i] <= arr[j]`. This implies `i` must be within the initial non-decreasing prefix of `arr`, and `j` must be within the initial non-decreasing suffix of `arr`.

First, we identify the longest non-decreasing prefix, ending at index `left`. Then, we find the longest non-decreasing suffix, starting at index `right`. If `left >= right`, the array is already sorted.

Otherwise, we have three options:
1.  Keep the prefix `arr[0...left]` and remove the rest. Length to remove: `n - 1 - left`.
2.  Keep the suffix `arr[right...n-1]` and remove the rest. Length to remove: `right`.
3.  Merge a prefix `arr[0...i]` (with `i <= left`) and a suffix `arr[j...n-1]` (with `j >= right`). We want to find `i` and `j` that minimize the removed length `j - i - 1`, subject to `arr[i] <= arr[j]`. This can be done efficiently with two pointers, one scanning the prefix part and one scanning the suffix part.

```java
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; // Array is already sorted
        }
        
        int right = n - 1;
        while (right > 0 && arr[right - 1] <= arr[right]) {
            right--;
        }
        
        // Case 1 & 2: Remove suffix or prefix
        int minLength = Math.min(n - 1 - left, right);
        
        // Case 3: Merge prefix and suffix
        int i = 0;
        int j = right;
        while (i <= left && j < n) {
            if (arr[i] <= arr[j]) {
                // Found a valid merge, remove arr[i+1...j-1]
                minLength = Math.min(minLength, j - i - 1);
                i++; // Try to extend the prefix
            } else {
                // arr[i] is too large, need a larger element from the suffix
                j++;
            }
        }
        
        return minLength;
    }
}
```
### Algorithm
- Find the rightmost index `left` such that the prefix `arr[0...left]` is non-decreasing. If `left` reaches the end of the array, it's already sorted, so return 0.
- Find the leftmost index `right` such that the suffix `arr[right...n-1]` is non-decreasing.
- The problem is now reduced to finding the shortest subarray to remove. There are three possibilities:
  1. Remove the suffix starting from `left + 1`. The length is `n - 1 - left`.
  2. Remove the prefix ending at `right - 1`. The length is `right`.
  3. Merge a part of the prefix `arr[0...i]` with a part of the suffix `arr[j...n-1]` where `i <= left` and `j >= right` and `arr[i] <= arr[j]`. The removed length is `j - i - 1`.
- Initialize `minLength` with the minimum of the first two cases.
- Use a two-pointer technique to find the best merge. Initialize `i = 0` and `j = right`.
- Iterate while `i <= left` and `j < n`:
  - If `arr[i] <= arr[j]`, we have a valid merge. Update `minLength = min(minLength, j - i - 1)` and increment `i` to try a longer prefix.
  - Otherwise, `arr[i]` is too large, so increment `j` to find a larger element in the suffix.
- Return the final `minLength`.

# Solutions
### Java

```java
class Solution {
public
  int findLengthOfShortestSubarray(int[] arr) {
    int n = arr.length;
    int i = 0, j = n - 1;
    while (i + 1 < n && arr[i] <= arr[i + 1]) {
      ++i;
    }
    while (j - 1 >= 0 && arr[j - 1] <= arr[j]) {
      --j;
    }
    if (i >= j) {
      return 0;
    }
    int ans = Math.min(n - i - 1, j);
    for (int l = 0; l <= i; ++l) {
      int r = search(arr, arr[l], j);
      ans = Math.min(ans, r - l - 1);
    }
    return ans;
  }
private
  int search(int[] arr, int x, int left) {
    int right = arr.length;
    while (left < right) {
      int mid = (left + right) >> 1;
      if (arr[mid] >= x) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int findLengthOfShortestSubarray(vector<int> &arr) {
    int n = arr.size();
    int i = 0, j = n - 1;
    while (i + 1 < n && arr[i] <= arr[i + 1]) {
      ++i;
    }
    while (j - 1 >= 0 && arr[j - 1] <= arr[j]) {
      --j;
    }
    if (i >= j) {
      return 0;
    }
    int ans = min(n - 1 - i, j);
    for (int l = 0; l <= i; ++l) {
      int r = lower_bound(arr.begin() + j, arr.end(), arr[l]) - arr.begin();
      ans = min(ans, r - l - 1);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int: n = len(arr) i, j = 0, n - 1 while i + 1 < n and arr[i] <= arr[i + 1]: i += 1 while j - 1 >= 0 and arr[j - 1] <= arr[j]: j -= 1 if i >= j: return 0 ans = min(n - i - 1, j) for l in range(i + 1): r = bisect_left(arr, arr[l], lo=j) ans = min(ans, r - l - 1) return ans

```