Shortest Subarray to be Removed to Make Array Sorted solution and explanation
Google
9 more videos on this problem
Shortest Subarray to be Removed to Make Array Sorted - Leetcode 1574 - PythonNeetCodeIO · 23:58 · 15K views
Shortest Subarray to be Removed to Make Array Sorted | Detailed | Leetcode 1574 | codestorywithMIKcodestorywithMIK · 34:17 · 12K views
shortest subarray to be removed to make array sorted leetcode | leetcode 1574Naresh Gupta · 8:20 · 9K views
Shortest Subarray to be Removed to Make Array Sorted | Leetcode 1574Techdose · 17:47 · 7K views
1574. Shortest Subarray to be Removed to Make Array Sorted | Binary Search | 2 PointersAryan Mittal · 14:23 · 3K views
LeetCode 1574. Shortest Subarray to be Removed to Make Array SortedHappy Coding · 21:56 · 3K views
1574. Shortest Subarray to be Removed to Make Array Sorted || Leetcode Daily - 15-11-2024side codes · 9:58 · 231 views
1574. Shortest Subarray to be Removed to Make Array Sorted | Two Pointers | Leetcode Daily ChallengeLeetQuest · 11:57 · 136 views
Shortest Subarray to be Removed to Make Array Sorted | Leetcode 1574 | Java Code | Developer CoderDeveloper Coder · 13:31 · 86 views
LeetCode : 1574 Shortest Subarray to be Removed to Make Array SortedThe algorithm Architect · 7:30 · 60 views
The 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 <= 1050 <= arr[i] <= 109
Approach overview
Problem Overview: You get an integer array. Remove exactly one contiguous subarray so the remaining elements form a non‑decreasing array. The goal is to minimize the length of the removed segment.
Approach 1: Two Pointer Technique (O(n) time, O(1) space)
Start by identifying the longest non‑decreasing prefix from the left and the longest non‑decreasing suffix from the right. If the entire array is already sorted, the answer is 0. Otherwise, treat the prefix and suffix as two valid sorted regions. Use a two pointers strategy: keep one pointer in the prefix and another in the suffix, and attempt to join them while preserving sorted order. If arr[left] <= arr[right], the subarray between them can be removed, so update the minimum length. If not, advance the right pointer to find a valid join point. This approach works because both regions are already sorted, allowing a linear merge-style scan. Time complexity is O(n) with O(1) extra space.
Approach 2: Binary Search for Optimal Join Point (O(n log n) time, O(1) space)
Again compute the longest sorted prefix and suffix. Instead of scanning the suffix with a pointer, iterate through each element in the prefix and find the earliest valid position in the suffix where the value can attach while keeping the array sorted. Since the suffix is already sorted, you can apply binary search to locate the first element greater than or equal to the current prefix value. The subarray between these indices becomes the removal candidate. Track the minimum removal length across all prefix elements. This approach is useful if you prefer explicit search logic over pointer movement. Time complexity is O(n log n) with constant auxiliary space.
The core insight behind both solutions is recognizing that only one middle segment needs removal. The left and right parts must individually remain sorted and also connect correctly. Identifying maximal sorted boundaries turns the problem into merging two sorted regions inside an array.
Recommended for interviews: The Two Pointer solution is what most interviewers expect. It runs in linear time and demonstrates strong reasoning about sorted segments and pointer movement. Mentioning the binary search variant shows you can exploit sorted structure in multiple ways, but the O(n) two‑pointer merge usually earns the best signal.
Approach 1: Two Pointer Technique
This approach uses two pointers to identify the first breaking point from both ends of the array and then calculates the minimum subarray length to remove by exploring combinations that can join two sorted parts.
Initialize two pointers, left starting from index 0 and right starting from the last index. First, traverse from the start until you find a break in the non-decreasing order to mark the left boundary. Similarly, traverse from the end to find the right boundary where a decrease occurs compared to the previous element.
Once both pointers are positioned correctly, slide the left pointer through the possible combinations and find the smallest subarray that can be removed to make the rest of the array sorted.
def findLengthOfShortestSubarray(arr):
n = len(arr)
left, right = 0, n - 1
# Find the first breaking point from the start
while left < n - 1 and arr[left] <= arr[left + 1]:
left += 1
# If the array is already non-decreasing
if left == n - 1:
return 0
# Find the first breaking point from the end
while right > 0 and arr[right - 1] <= arr[right]:
right -= 1
# Result can be either removing one of the segments entirely
result = min(n - left - 1, right)
# Combine a valid prefix and suffix
i, j = 0, right
while i <= left and j < n:
if arr[i] <= arr[j]:
result = min(result, j - i - 1)
i += 1
else:
j += 1
return result
# Example usage:
arr = [1, 2, 3, 10, 4, 2, 3, 5]
print(findLengthOfShortestSubarray(arr))public class Solution {
public int findLengthOfShortestSubarray(int[] arr) {
int n = arr.length;
int left = 0, right = n - 1;
// Find first breaking point from the start
while (left < n - 1 && arr[left] <= arr[left + 1]) {
left++;
}
// Already sorted
if (left == n - 1) return 0;
// Find first breaking point from the end
while (right > 0 && arr[right - 1] <= arr[right]) {
right--;
}
// Minimum of removing left part or right part entirely
int result = Math.min(n - left - 1, right);
// Attempt to merge prefix and suffix
int i = 0, j = right;
while (i <= left && j < n) {
if (arr[i] <= arr[j]) {
result = Math.min(result, j - i - 1);
i++;
} else {
j++;
}
}
return result;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] arr = {1, 2, 3, 10, 4, 2, 3, 5};
System.out.println(sol.findLengthOfShortestSubarray(arr));
}
}The above code first finds the longest non-decreasing subarray from the start and end of the array using two pointers, left and right. After determining these points, it attempts to merge these sorted segments by sliding through potential combinations and returns the minimal length of the subarray to be removed.
Time complexity: O(n), where n is the length of the array since we traverse the array twice with additional O(n) operations.
Space complexity: O(1), as no extra space is used, except for a few variables.
Approach 2: Binary Search for Optimal Join Point
This approach leverages binary search to efficiently find the optimal 'join point' between a sorted prefix and suffix. By keeping track of sorted segments from both ends, binary search is used to quickly determine the minimum subarray to remove by checking suitable merge points.
First, determine the lengths of sorted segments from the beginning and end. Then, use binary search to identify an index where blending the end and start segments maintains the non-decreasing order.
import bisect
def findLengthOfShortestSubarray(arr):
n = len(arr)
# Find longest non-decreasing prefix
left = 0
while left < n - 1 and arr[left] <= arr[left + 1]:
left += 1
# If it's already sorted
if left == n - 1:
return 0
# Find longest non-decreasing suffix
right = n - 1
while right > 0 and arr[right - 1] <= arr[right]:
right -= 1
result = min(n - left - 1, right)
# Optimize using binary search to find the best merge point
for i in range(left + 1):
j = bisect.bisect_left(arr, arr[i], right, n)
result = min(result, j - i - 1)
return result
# Example usage
arr = [1, 2, 3, 10, 4, 2, 3, 5]
print(findLengthOfShortestSubarray(arr))#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int findLengthOfShortestSubarray(vector<int>& arr) {
int n = arr.size();
// Find longest non-decreasing prefix
int left = 0;
while (left < n - 1 && arr[left] <= arr[left + 1]) {
left++;
}
// If it's already sorted
if (left == n - 1) return 0;
// Find longest non-decreasing suffix
int right = n - 1;
while (right > 0 && arr[right - 1] <= arr[right]) {
right--;
}
int result = min(n - left - 1, right);
// Use binary search for optimal merging
for (int i = 0; i <= left; i++) {
int j = lower_bound(arr.begin() + right, arr.end(), arr[i]) - arr.begin();
result = min(result, j - i - 1);
}
return result;
}
int main() {
vector<int> arr = {1, 2, 3, 10, 4, 2, 3, 5};
cout << findLengthOfShortestSubarray(arr) << endl;
return 0;
}This implementation identifies sorted prefix and suffix ranges and uses binary search to determine the minimal join point. It calculates and returns the smallest segment required for removal to satisfy the sorted property of the remaining array.
Time complexity: O(n log n), due to the binary search operations.
Space complexity: O(1).
Approach 3: Two Pointers + Binary Search
First, we find the longest non-decreasing prefix and the longest non-decreasing suffix of the array, denoted as nums[0..i] and nums[j..n-1], respectively.
If i geq j, it means the array is already non-decreasing, so we return 0.
Otherwise, we can choose to delete the right suffix or the left prefix. Therefore, initially, the answer is min(n - i - 1, j).
Next, we enumerate the right endpoint l of the left prefix. For each l, we can use binary search to find the first position greater than or equal to nums[l] in nums[j..n-1], denoted as r. At this point, we can delete nums[l+1..r-1] and update the answer ans = min(ans, r - l - 1). Continue enumerating l to get the final answer.
The time complexity is O(n times log n), where n is the length of the array. The space complexity is O(1).
func findLengthOfShortestSubarray(arr []int) int {
n := len(arr)
i, j := 0, n-1
for i+1 < n && arr[i] <= arr[i+1] {
i++
}
for j-1 >= 0 && arr[j-1] <= arr[j] {
j--
}
if i >= j {
return 0
}
ans := min(n-i-1, j)
for l := 0; l <= i; l++ {
r := j + sort.SearchInts(arr[j:], arr[l])
ans = min(ans, r-l-1)
}
return ans
}Approach 4: Two Pointers
Similar to Solution 1, we first find the longest non-decreasing prefix and the longest non-decreasing suffix of the array, denoted as nums[0..i] and nums[j..n-1], respectively.
If i geq j, it means the array is already non-decreasing, so we return 0.
Otherwise, we can choose to delete the right suffix or the left prefix. Therefore, initially, the answer is min(n - i - 1, j).
Next, we enumerate the right endpoint l of the left prefix. For each l, we directly use two pointers to find the first position greater than or equal to nums[l] in nums[j..n-1], denoted as r. At this point, we can delete nums[l+1..r-1] and update the answer ans = min(ans, r - l - 1). Continue enumerating l to get the final answer.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
function findLengthOfShortestSubarray(arr) {
let [l, r, n] = [0, arr.length - 1, arr.length];
while (r && arr[r - 1] <= arr[r]) r--;
if (r === 0) return 0;
let ans = r;
while (l < r && (!l || arr[l - 1] <= arr[l])) {
while (r < n && arr[l] > arr[r]) r++;
ans = Math.min(ans, r - l - 1);
l++;
}
return ans;
}function findLengthOfShortestSubarray(arr: number[]): number {
let [l, r, n] = [0, arr.length - 1, arr.length];
while (r && arr[r - 1] <= arr[r]) r--;
if (r === 0) return 0;
let ans = r;
while (l < r && (!l || arr[l - 1] <= arr[l])) {
while (r < n && arr[l] > arr[r]) r++;
ans = Math.min(ans, r - l - 1);
l++;
}
return ans;
}func findLengthOfShortestSubarray(arr []int) int {
n := len(arr)
i, j := 0, n-1
for i+1 < n && arr[i] <= arr[i+1] {
i++
}
for j-1 >= 0 && arr[j-1] <= arr[j] {
j--
}
if i >= j {
return 0
}
ans := min(n-i-1, j)
r := j
for l := 0; l <= i; l++ {
for r < n && arr[r] < arr[l] {
r += 1
}
ans = min(ans, r-l-1)
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Two Pointer Technique | Time complexity: O(n), where n is the length of the array since we traverse the array twice with additional O(n) operations. |
| Binary Search for Optimal Join Point | Time complexity: O(n log n), due to the binary search operations. |
| Two Pointers + Binary Search | – |
| Two Pointers | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Pointer Technique | O(n) | O(1) | Best overall approach. Linear scan that merges sorted prefix and suffix efficiently. |
| Binary Search Join Point | O(n log n) | O(1) | Useful when reasoning about sorted suffix searches or when implementing explicit search logic. |
| Brute Force Removal Check | O(n^2) | O(1) | Conceptual baseline for understanding the problem before optimizing. |
Frequently asked questions
Is Shortest Subarray to be Removed to Make Array Sorted easy or hard?
The problem is classified as Medium difficulty. The main challenge is recognizing that the answer involves merging the longest sorted prefix and suffix rather than trying all possible removals.
Shortest Subarray to be Removed to Make Array Sorted Python/Java solution
Python and Java implementations typically use the two-pointer method. First compute the sorted prefix and suffix boundaries, then adjust pointers to find the minimal removable window. The logic remains identical across languages and maintains O(n) time complexity.
How to solve Shortest Subarray to be Removed to Make Array Sorted in O(n)?
Scan from the left to find the longest sorted prefix and from the right to find the longest sorted suffix. Then use two pointers to attempt to connect elements from the prefix to the suffix while maintaining non-decreasing order. The minimal distance between these pointers represents the subarray to remove.
What is the best approach for Shortest Subarray to be Removed to Make Array Sorted?
The best approach uses the two pointer technique. First identify the longest non-decreasing prefix and suffix. Then move two pointers across these regions to find the smallest gap that can be removed while keeping the array sorted. This solution runs in O(n) time with O(1) extra space.
Is Shortest Subarray to be Removed to Make Array Sorted asked at Google/Amazon/Meta?
This problem is commonly used in interviews at companies that emphasize array manipulation and pointer techniques, including Google, Amazon, and Meta-style interview loops. It tests reasoning about sorted segments and optimization from brute force to linear time.
What data structure is used in Shortest Subarray to be Removed to Make Array Sorted?
The problem primarily uses arrays with algorithmic techniques such as two pointers and binary search. Some conceptual discussions also relate to monotonic properties similar to monotonic stacks, but the optimal implementation only requires pointer manipulation.
What is the time complexity of Shortest Subarray to be Removed to Make Array Sorted?
The optimal solution runs in O(n) time because each element is processed at most once while scanning the prefix and suffix with two pointers. Space complexity is O(1) since only a few index variables are used.