Shortest Subarray to be Removed to Make Array Sorted - Solution & Explanation
Problem Statement
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.
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.
Complexity
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.
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.
Complexity
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).
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).
Code
Python
Java
C++
Go
TypeScript
JavaScript
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 | — |
Detailed 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. |
Video Solution
Shortest Subarray to be Removed to Make Array Sorted - Leetcode 1574 - Python • NeetCodeIO • 15,431 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Shortest Subarray to be Removed to Make Array Sorted easy or hard?
Shortest Subarray to be Removed to Make Array Sorted Python/Java solution
How to solve Shortest Subarray to be Removed to Make Array Sorted in O(n)?
What is the best approach for Shortest Subarray to be Removed to Make Array Sorted?
Is Shortest Subarray to be Removed to Make Array Sorted asked at Google/Amazon/Meta?
What data structure is used in Shortest Subarray to be Removed to Make Array Sorted?
What is the time complexity of Shortest Subarray to be Removed to Make Array Sorted?
Ready to solve this problem?
Practice Shortest Subarray to be Removed to Make Array Sorted with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor