Watch 10 video solutions for Shortest Subarray to be Removed to Make Array Sorted, a medium level problem involving Array, Two Pointers, Binary Search. This walkthrough by NeetCodeIO has 14,989 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 109Problem 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 | 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. |