Shortest Subarray to be Removed to Make Array Sorted

Medium
1356.

Shortest Subarray to be Removed to Make Array Sorted

Shortest Subarray to be Removed to Make Array Sorted is a medium coding problem on arrays, binary search and two pointers, asked in Amazon, Google, Meta and Razorpay interviews.

Given an integer array arr, remove one contiguous subarray (possibly empty) so that the elements left behind, kept in their original order, are non-decreasing.

Return the length of the shortest subarray you can remove.

Example 1

Input
arr = [1,3,4,12,5,3,4,6]
Output
3
Explanation
Remove `[12,5,3]` to keep `[1,3,4,4,6]` (removing `[4,12,5]` also works). No two elements can be removed to fix it.

Example 2

Input
arr = [9,7,5,3,1]
Output
4
Explanation
The array is strictly decreasing, so only one element can stay.

Example 3

Input
arr = [2,2,5]
Output
0
Explanation
It is already non-decreasing.

Constraints

  • 1 <= arr.length <= 10^5
  • 0 <= arr[i] <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {number}
 */
var findLengthOfShortestSubarray = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Shortest Subarray to be Removed to Make Array Sorted Solution

Shortest Subarray to be Removed to Make Array Sorted solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Shortest Subarray to be Removed to Make Array Sorted is a medium coding problem on arrays, binary search and two pointers, asked in Amazon, Google, Meta and Razorpay interviews.

Problem statement

Given an integer array arr, remove one contiguous subarray (possibly empty) so that the elements left behind, kept in their original order, are non-decreasing.

Return the length of the shortest subarray you can remove.

Example 1

Input: arr = [1,3,4,12,5,3,4,6]
Output: 3
Explanation: Remove `[12,5,3]` to keep `[1,3,4,4,6]` (removing `[4,12,5]` also works). No two elements can be removed to fix it.

Example 2

Input: arr = [9,7,5,3,1]
Output: 4
Explanation: The array is strictly decreasing, so only one element can stay.

Example 3

Input: arr = [2,2,5]
Output: 0
Explanation: It is already non-decreasing.

Constraints

  • 1 <= arr.length <= 10^5
  • 0 <= arr[i] <= 10^9

Hints for Shortest Subarray to be Removed to Make Array Sorted

  1. Hint 1

    What remains is a prefix of arr followed by a suffix of arr, and each of them must be non-decreasing on its own.

  2. Hint 2

    Find the longest non-decreasing prefix arr[0..l] and the longest non-decreasing suffix arr[r..n-1]. Keeping only one of them gives the candidates n - l - 1 and r.

  3. Hint 3

    To keep part of both, walk i through the prefix and a pointer j through the suffix: advance j until arr[j] >= arr[i]; then removing arr[i+1..j-1] works. Both pointers only move forward.

How to solve Shortest Subarray to be Removed to Make Array Sorted

The kept elements are a prefix plus a suffix. The prefix must lie inside the longest sorted prefix, the suffix inside the longest sorted suffix, and they must join without a drop — two pointers find the best join.

Approach

  1. Let l be the last index of the longest non-decreasing prefix. If l == n - 1, return 0.
  2. Let r be the first index of the longest non-decreasing suffix.
  3. Start with ans = min(n - l - 1, r) (keep only the prefix, or only the suffix).
  4. Set j = r. For each i from 0 to l: advance j while j < n and arr[j] < arr[i]; then update ans = min(ans, j - i - 1).
  5. Return ans.

Why it works

Any valid removal keeps arr[0..i] and arr[j..n-1] for some i < j, with both pieces sorted and arr[i] <= arr[j]. For a fixed i, the best j is the first suffix index whose value is at least arr[i] (the suffix is sorted, so all later ones also work but remove more). As i increases, arr[i] does not decrease inside the sorted prefix, so that first j never moves back — every (i, j) candidate is examined in one forward pass.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Handle the already-sorted case first; otherwise the suffix scan and the prefix overlap.
  • Do not forget the two one-sided options (keep only the prefix or only the suffix) — the joint loop may not cover them when no join exists.
  • "Sorted" means non-decreasing here, so equal neighbours are fine: compare with <=.

Reference solution

Python

from typing import List

def findLengthOfShortestSubarray(arr: List[int]) -> int:
    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)
    j = r
    for i in range(l + 1):
        while j < n and arr[j] < arr[i]:
            j += 1
        ans = min(ans, j - i - 1)
    return ans

Java

public static int findLengthOfShortestSubarray(int[] arr) {
    int n = arr.length;
    int 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 j = r;
    for (int i = 0; i <= l; i++) {
        while (j < n && arr[j] < arr[i]) j++;
        ans = Math.min(ans, j - i - 1);
    }
    return ans;
}

C++

int findLengthOfShortestSubarray(vector<int>& arr) {
    int n = arr.size();
    int 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 j = r;
    for (int i = 0; i <= l; i++) {
        while (j < n && arr[j] < arr[i]) j++;
        ans = min(ans, j - i - 1);
    }
    return ans;
}

JavaScript

var findLengthOfShortestSubarray = function(arr) {
    var n = arr.length;
    var l = 0;
    while (l + 1 < n && arr[l] <= arr[l + 1]) l++;
    if (l === n - 1) return 0;
    var r = n - 1;
    while (r > 0 && arr[r - 1] <= arr[r]) r--;
    var ans = Math.min(n - l - 1, r);
    var j = r;
    for (var i = 0; i <= l; i++) {
        while (j < n && arr[j] < arr[i]) j++;
        ans = Math.min(ans, j - i - 1);
    }
    return ans;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Search