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.
- Difficulty: Medium
- Topics: Arrays, Binary Search, Two Pointers, Monotonic Stack
- Asked at: Amazon, Google, Meta, Razorpay
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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^50 <= arr[i] <= 10^9
Hints for Shortest Subarray to be Removed to Make Array Sorted
Hint 1
What remains is a prefix of
arrfollowed by a suffix ofarr, and each of them must be non-decreasing on its own.Hint 2
Find the longest non-decreasing prefix
arr[0..l]and the longest non-decreasing suffixarr[r..n-1]. Keeping only one of them gives the candidatesn - l - 1andr.Hint 3
To keep part of both, walk
ithrough the prefix and a pointerjthrough the suffix: advancejuntilarr[j] >= arr[i]; then removingarr[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
- Let
lbe the last index of the longest non-decreasing prefix. Ifl == n - 1, return 0. - Let
rbe the first index of the longest non-decreasing suffix. - Start with
ans = min(n - l - 1, r)(keep only the prefix, or only the suffix). - Set
j = r. For eachifrom 0 tol: advancejwhilej < nandarr[j] < arr[i]; then updateans = min(ans, j - i - 1). - 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 ansJava
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