Shortest subarray to be removed to make array sorted

Array Two Pointers Binary Search Stack Monotonic Stack

51.3% acceptance

Feb 25, 2026

2452

163

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.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn find_length_of_shortest_subarray(arr: Vec<i32>) -> i32 {
    let n = arr.len();
    // Find longest non-decreasing prefix
    let mut left = 0;
    while left + 1 < n && arr[left] <= arr[left + 1] {
      left += 1;
    }
    if left == n - 1 {
      return 0; // already sorted
    }
    // Find longest non-decreasing suffix
    let mut right = n - 1;
    while right > 0 && arr[right - 1] <= arr[right] {
      right -= 1;
    }

    // Option 1: remove everything after left
    // Option 2: remove everything before right
    let mut res = (n - left - 1).min(right) as i32;

    // Option 3: merge prefix[0..=i] with suffix[j..n-1]
    let mut i = 0;
    let mut j = right;
    while i <= left && j < n {
      if arr[i] <= arr[j] {
        res = res.min((j - i - 1) as i32);
        i += 1;
      } else {
        j += 1;
      }
    }
    res
  }
}