Shortest Subarray to be Removed to Make Array Sorted

medium array two pointers binary search stack monotonic stack

Problem

Given arr, remove a contiguous subarray (possibly empty) so the rest is non-decreasing. Return the minimum length to remove.

Inputarr = [1,2,3,10,4,2,3,5]

Output3

Remove [10,4,2] to leave [1,2,3,3,5].

arr

def find_length_of_shortest_subarray(arr):
    n = len(arr); L = 0
    while L + 1 < n and arr[L] <= arr[L + 1]: L += 1
    if L == n - 1: return 0
    R = n - 1
    while R > 0 and arr[R - 1] <= arr[R]: R -= 1
    ans = min(n - L - 1, R)
    i, j = 0, R
    while i <= L and j < n:
        if arr[i] <= arr[j]:
            ans = min(ans, j - i - 1); i += 1
        else:
            j += 1
    return ans

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

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

int findLengthOfShortestSubarray(vector& arr) {
    int n = arr.size(), L = 0;
    while (L + 1 < n && arr[L] <= arr[L + 1]) L++;
    if (L == n - 1) return 0;
    int R = n - 1;
    while (R > 0 && arr[R - 1] <= arr[R]) R--;
    int ans = min(n - L - 1, R);
    int i = 0, j = R;
    while (i <= L && j < n) {
        if (arr[i] <= arr[j]) { ans = min(ans, j - i - 1); i++; }
        else j++;
    }
    return ans;
}

Explanation

Whatever subarray we remove, the part that stays must be a non-decreasing prefix followed by a non-decreasing suffix, glued together at the boundary. So the plan is: find the longest sorted prefix and suffix, then figure out the smallest gap we can cut between them.

First we extend L as far right as the array stays sorted (the prefix ends at L), and extend R as far left as the suffix stays sorted (the suffix starts at R). If the prefix already reaches the end, the array is sorted and the answer is 0.

A baseline answer is to drop everything except one side: min(n - L - 1, R). Then we try to keep some of both sides with two pointers i (over the prefix) and j (over the suffix). Whenever arr[i] <= arr[j], joining prefix up to i with suffix from j is valid, removing the gap j - i - 1; we record it and advance i. Otherwise we move j forward to find a larger suffix value.

We keep the minimum gap found across all valid joins. Because both pointers only move forward, the merge is a single linear sweep.

Example: arr = [1,2,3,10,4,2,3,5]. Prefix is [1,2,3,10] (L = 3), suffix is [2,3,5] (R = 5). Matching 1,2,3 against the suffix lets us keep [1,2,3] and [2,3,5], removing [10,4,2] — length 3.

Time: O(n) Space: O(1)