1574. Shortest Subarray to be Removed to Make Array Sorted - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement:

Given an integer array arr, you need to remove one contiguous subarray (possibly empty) such that the remaining elements form a non-decreasing (sorted) array. In other words, after removing a continuous chunk from the array, the elements left in the original order should be sorted in non-decreasing order (each element is >= the previous one). You are asked to find the length of the shortest subarray that can be removed to achieve this.

Example 1:
Input: arr = [1, 2, 3, 10, 4, 2, 3, 5]
Output: 3
Explanation: We can remove the subarray [10, 4, 2] (of length 3) to get the remaining array [1, 2, 3, 3, 5], which is non-decreasing. Another valid removal is [3, 10, 4] (also length 3), leaving [1, 2, 2, 3, 5] sorted.
Example 2:
Input: arr = [5, 4, 3, 2, 1]
Output: 4
Explanation: The array is strictly decreasing, so we can only keep one element. Removing any 4 out of the 5 elements will leave a single element, which is trivially sorted. For instance, remove [5, 4, 3, 2] to leave [1], or remove [4, 3, 2, 1] to leave [5].
Example 3:
Input: arr = [1, 2, 3]
Output: 0
Explanation: The array is already non-decreasing, so we don’t need to remove any elements. (Removing an empty subarray is allowed, resulting in no change.)
Example 4:
Input: arr = [1, 1, 1, 0, 1, 1]
Output: 3
Explanation: The array is almost sorted except for the 0 that disrupts the order. We can remove the subarray [1, 0, 1] (length 3) to get the remaining array [1, 1, 1, 1], which is non-decreasing.

Constraints:

1 <= arr.length <= 100,000
0 <= arr[i] <= 10^9
The subarray to remove can be empty (meaning if the array is already sorted, answer is 0).
The remaining elements (after removal) must retain their original order from the original array and be non-decreasing.

Hints Section:

Start with simple cases: Check if the array is already sorted (then answer is 0) or if it’s strictly decreasing (then you must remove everything except one element, so answer is n-1, where n is the array length). Identifying these edge cases can give immediate answers or clues.
Consider sorted prefixes and suffixes: Find the longest prefix (from the start) that is already sorted in non-decreasing order, and the longest suffix (from the end) that is sorted. These represent portions of the array that are “safe” (already sorted). Any subarray we remove will be somewhere in the middle, between this sorted prefix and sorted suffix.
Merge the sorted parts carefully: Once you have a sorted prefix and suffix, think about how to connect them after removing a middle subarray. The last element of the prefix must be <= the first element of the suffix to keep the array sorted after removal. You might try different breakpoints where the prefix ends and the suffix begins. This can be done efficiently using two pointers or binary search because the prefix and suffix parts are sorted.

Approaches:

Brute Force Approach: The brute force solution tries every possible subarray removal and checks if the remaining array is sorted. While this guarantees finding the answer, it’s extremely inefficient for large arrays.

Logic:
- Iterate over all possible starting indices i for the subarray to remove.
- For each i, iterate over all possible ending indices j >= i for the subarray to remove. This means we are considering removing the subarray arr[i...j].
- Construct the remaining array by skipping elements from index i to j. Check if this remaining array is sorted (each element <= next element).
- Track the minimum length of a subarray that yields a sorted remaining array.
- Return the minimum length found.
Why it works: This method brute-forces all choices of contiguous elements to remove, so it will definitely find the shortest valid removal. It simply checks every possibility.

Python Implementation (Brute Force):

Python3

. . . .

Java Implementation (Brute Force):

Java

. . . .

In the Java code above, we combined checking the sorted order of the remaining prefix and suffix directly in the loops to avoid creating new arrays for each check. We ensure the left part (before the removed subarray) is sorted, the right part (after the removed subarray) is sorted, and also that the last element of the left part is <= the first element of the right part. If all conditions hold, the remaining array would be sorted after removing arr[i..j]. This is still very slow for large n.

Time Complexity: The brute force approach is extremely inefficient. In the worst case, we check every possible subarray to remove. There are O(n²) possible subarrays, and checking if the remaining array is sorted takes O(n) time in the worst case. This leads to O(n³) time complexity for the naive implementation. Even with minor optimizations, it’s not feasible for n as large as 100k. For example, if n = 100,000, an O(n³) algorithm is completely impractical.

Space Complexity: O(n) in the worst case if we create a new array for the remaining elements to check sortedness (as in the Python approach). In the optimized Java check, we use O(1) extra space (just a few variables) since we check in-place without constructing new arrays.

Summary: Brute force is useful to understand the problem (trying all possibilities), but we need a much more efficient strategy to handle large inputs within a reasonable time.

Optimal Approach: To solve this efficiently, we need to use the sorted structure of the array’s parts to our advantage. The key insight is to keep as much of the array’s sorted parts as possible, and only remove the necessary middle portion. We can do this in linear or near-linear time by following these steps:

Step-by-Step Logic:
- Find the longest sorted prefix: Traverse from the beginning of arr and find the longest prefix that is already sorted in non-decreasing order. Let L be the index where this sorted prefix ends. That means arr[0..L] is sorted, but arr[L] > arr[L+1] (if L is not the last index) is where the sorted order breaks.
- Find the longest sorted suffix: Similarly, traverse from the end and find the longest suffix that is sorted. Let R be the starting index of this sorted suffix, so arr[R..n-1] is sorted, and arr[R-1] > arr[R] is the point where the order breaks from the right side.
- At this point, arr[0..L] (prefix) is sorted and arr[R..n-1] (suffix) is sorted. Any subarray we remove must cover the region between these two sorted parts (because outside of them everything is already in order). If the entire array was sorted to begin with, we would find that L ends up being the last index (L = n-1) or R ends up being 0, and we can return 0 immediately.
- Initial candidate removals: Consider two simple possibilities:
  1. Remove everything after the sorted prefix. This would mean removing arr[L+1 ... n-1]. The length of this removal would be n - (L+1) = n - L - 1. This works because we keep the prefix which is sorted, and remove the rest of the array.
  2. Remove everything before the sorted suffix. This means removing arr[0 ... R-1]. The length of this removal would be R - 0 = R. This works because we keep the suffix which is sorted, and remove the entire prefix portion.
  We take ans = min(n - L - 1, R) as an initial answer – the smaller of these two large removals. This ensures the array is sorted but may not be the shortest removal.
- Connect prefix and suffix: The optimal solution may be to remove a subarray in the middle, keeping some of the prefix and some of the suffix. To do this optimally, we want to maximize the portion of the prefix we keep and the portion of the suffix we keep such that they still connect in sorted order. Essentially, we need to find a boundary where the end of the prefix is <= the start of the suffix.
  
  Here's how to find that boundary efficiently:
  - Two-pointer method: Place one pointer at the end of the sorted prefix (i = L) and another at the start of the sorted suffix (j = R). We will try to shrink the gap between them.
    - If arr[i] <= arr[j], it means the current prefix end can directly connect to the current suffix start without breaking order. Thus, removing the subarray between i and j (i.e., arr[i+1 ... j-1]) is a valid solution. We record the length of this removal and try to minimize it. To potentially do even better, we can move the prefix pointer leftwards (decrease i) to see if we can keep an even larger prefix while still maintaining order.
    - If arr[i] > arr[j], it means the prefix element is too large to connect to the suffix at j. In this case, we need to move the suffix pointer rightwards (increase j) to find a larger element in the suffix that might be >= arr[i]. In doing so, we’re considering removing a larger portion of the array (because j moves right, meaning we’re keeping less of the suffix), but it might be necessary to find a valid connection. We continue this process until we’ve tried all possible ways the prefix and suffix can meet.
    - Each time we find arr[i] <= arr[j], we calculate the removal length j - i - 1 (elements between i and j) and update our answer ans with the minimum length found.
    This two-pointer process effectively checks all combinations of a prefix end and suffix start that can form a sorted remaining array, without explicitly testing every subarray. It runs in linear time because each pointer only moves at most n steps in total.
  - Binary search method: Alternatively, since the suffix part arr[R..n-1] is sorted, for each possible prefix endpoint you can binary search in the suffix to find the smallest element that is >= the prefix’s last element. For example, for each index l from 0 to L, find the lowest index r >= R such that arr[r] >= arr[l]. That r marks where the suffix can start if we keep prefix up to l. The removal in that case is arr[l+1 ... r-1]. Using binary search for each l results in an O(n log n) algorithm. (We will implement this approach below for clarity.)
Key observations that drive this solution:
- The array outside the subarray we remove must remain sorted. That’s why we focus on the already sorted prefix and suffix. Any disruption to sorted order must lie in the middle and will be removed.
- Once we have the largest sorted prefix and suffix, the only candidates for removal are those that bridge between some point in the prefix and some point in the suffix. We don't need to consider removing any part that goes into the sorted prefix or beyond the sorted suffix because that would be unnecessary removal of already sorted regions.
- Ensuring the connection prefix_end <= suffix_start is crucial. If this condition holds, then the remaining array (prefix + suffix) is sorted. If it doesn’t, we need to adjust the boundary.

Python Implementation (Optimal):

Python3

. . . .

In this Python code, we first compute the sorted prefix (L) and suffix (R). Then we try to find the minimal gap. We use two pointers i and j: i goes from 0 up to L (trying different prefix end positions), and j starts at R and moves right as needed. When arr[i] <= arr[j], it means the subarray between i and j can be removed. We update ans with the length of that removal and then increment i to attempt keeping a larger prefix. If arr[i] > arr[j], we increment j (meaning we decide to remove a larger portion, pushing the suffix start further right). This finds the minimal removal length that allows arr[i] <= arr[j].

Java Implementation (Optimal):

Java

. . . .

In the Java code above, we used a combination of logic and the built-in Arrays.binarySearch to find the correct position in the suffix for each possible prefix end i. For each i up to L, we determine the smallest suffix index rIndex such that arr[rIndex] >= arr[i]. The removal would then be from i+1 to rIndex-1. We update ans with the smallest such removal. If arr[i] is already <= arr[R] (the first element of the suffix), then the suffix can start at R when prefix ends at i, so the removal is R - i - 1. This yields the same result as the two-pointer approach.

Time Complexity: This optimal approach runs in O(n) or O(n log n) time, depending on how it’s implemented. The two-pointer method is O(n) because each pointer moves at most n steps total. The binary search method is O(n log n) because for each of up to n prefix elements we do a binary search on the suffix (log n). In either case, this is efficient enough for n = 100,000 (e.g., 100k * log(100k) is on the order of 1.7 million operations, which is fine).

Space Complexity: O(1) extra space (we only use a few integer variables regardless of input size). We are not creating new large data structures, just scanning the array in place.

Step-by-Step Walkthrough:

Let’s walk through the optimal solution with a visual example to see how it works. Consider the array from Example 1:

arr = [1, 2, 3, 10, 4, 2, 3, 5]
          ^^^^^    ^^^^^^^

(We will use ^ brackets to denote the sorted prefix and suffix.)

Identify sorted prefix:
Traverse from the start:
- 1 <= 2 <= 3 <= 10 – so far so good.
- Next is 4, but 4 < 10 which breaks the non-decreasing order at index 4.
  So the longest sorted prefix is [1, 2, 3, 10] which ends at index L = 3 (value 10). This prefix is highlighted as ^^^^ above.
Identify sorted suffix:
Traverse from the end:
- 5 (last element).
- 3 <= 5 – good, suffix [3, 5] is sorted so far.
- 2 <= 3 – good, suffix [2, 3, 5] sorted.
- 4 > 2 – breaks order when moving left at index 4 (value 4 is not <= 2).
  So the longest sorted suffix is [2, 3, 5] starting at index R = 5 (value 2). This suffix is indicated by the second ^^^^^ portion above (the segment 2, 3, 5 at the end).
At this point:
- Sorted prefix is arr[0..3] = [1, 2, 3, 10].
- Sorted suffix is arr[5..7] = [2, 3, 5].
  The array looks like:
```
Prefix: [1, 2, 3, 10]  | middle unsorted part |  Suffix: [2, 3, 5]
        0  1  2   3    | 4    5    6         |   5  6  7   (indices)
```
(Note: index 4 is value 4, index 5 is 2, index 6 is 3, index 7 is 5.)
Check trivial removals:
Removing everything after index 3 (i.e., remove indices 4 through 7) would remove 4 elements and leave [1,2,3,10] which is sorted. Removing everything before index 5 (i.e., remove indices 0 through 4) would remove 5 elements and leave [2,3,5] which is sorted. So an initial answer is min(4, 5) = 4. But we can do better by removing a smaller subarray in the middle and keeping parts of both ends.
Bridge the prefix and suffix:
We need to find a place where the prefix and suffix can meet. The last element of the prefix (arr[L] = arr[3] = 10) is currently greater than the first element of the suffix (arr[R] = arr[5] = 2), so we can’t just connect them as is. We’ll try adjusting the boundary:
- Take a pointer i at the end of the prefix (index 3) and a pointer j at the start of the suffix (index 5). Compare arr[i] and arr[j]:
  arr[3] = 10, arr[5] = 2. Since 10 > 2, the prefix element is too large to directly connect with the suffix. To fix this, we move j to the right, looking for a larger suffix element that can connect with 10.
  Move j from 5 to 6: now arr[j] = arr[6] = 3. Compare with arr[3] = 10 again. 10 > 3, still not OK.
  
  Move j from 6 to 7: now arr[j] = arr[7] = 5. Compare with arr[3] = 10. 10 > 5, still not OK.
  Move j from 7 to beyond the array (j becomes 8 which is n). Now we’ve run out of suffix elements to compare with 10. This means we cannot keep the entire prefix up to index 3 if we want to connect to any suffix element – the value 10 is just too large. So index 3 (the value 10) likely needs to be removed or be part of the removed subarray.
- Let’s try a smaller prefix. Move pointer i left to index 2 (prefix now ending at value 3). Reset j to start at the original suffix start (index 5) for a fair comparison with this new prefix end.
  Now compare arr[2] = 3 with arr[5] = 2. 3 > 2, not OK. So move j right:
  j to 6: compare arr[2] = 3 with arr[6] = 3. Now 3 <= 3, this is good! We found that the prefix ending at index 2 (value 3) can connect to the suffix starting at index 6 (value 3). This means if we remove everything from index 3 up to index 5 (inclusive), the remaining array will be sorted.
  The subarray we’d remove in this case is indices [3, 4, 5] which corresponds to [10, 4, 2]. Check the remaining array: it would be [1, 2, 3] + [3, 5] = [1, 2, 3, 3, 5] which is indeed sorted. The length of this removal is 3.
- Could we do even better (shorter removal)? Let’s move i left again to index 1 (prefix ending at value 2) and try to connect with the suffix:
  arr[1] = 2 and arr[5] = 2. 2 <= 2, it connects immediately without moving j! This means prefix ending at index 1 (values [1, 2]) connects to suffix starting at index 5 (value 2). The subarray to remove would be from index 2 through index 4 ([3, 10, 4]). Remove those and the array becomes [1, 2] + [2, 3, 5] = [1, 2, 2, 3, 5], which is sorted. This removal is also length 3. It’s the other valid solution mentioned in the example. The length is 3, which ties with our current best.
- Finally, try i = 0 (prefix ending at value 1):
  arr[0] = 1 and arr[5] = 2. 1 <= 2, good connection. That means remove subarray from index 1 through 4. That subarray is [2, 3, 10, 4] of length 4, leaving [1] + [2, 3, 5] = [1, 2, 3, 5] which is sorted. Removal length 4 is worse than 3, so we wouldn’t choose this.
Among all these, the smallest removal length we found was 3 (there were two ways to achieve length 3). So the algorithm would output 3. We have effectively checked all relevant ways to connect a prefix and suffix and found the minimum gap that needs removal.
Result: 3, which matches the expected answer.

This walkthrough demonstrates how we progressively tried shorter prefixes (meaning a larger removal in the middle) until we found a point where the prefix’s end could connect with the suffix’s start. We didn’t have to try every possible subarray; we only examined the boundaries where sorted order could potentially be maintained.

Additional Insights:

Common Mistakes:
- Forgetting the subarray has to be contiguous: Some might think of removing scattered elements (which turns it into a longest increasing subsequence problem). Here, the removal must be one continuous block. Make sure your solution isn’t accidentally considering two separate smaller removals instead of one contiguous removal.
- Ignoring the prefix/suffix structure: It’s easy to get lost in trying random middle sections to remove. The sorted prefix and suffix give a clear structure — not using this can lead to either incorrect solutions or inefficient ones.
- Off-by-one errors in indices: When implementing, be careful with boundaries. For example, if you decide to remove arr[i..j], ensure that the remaining parts arr[0..i-1] and arr[j+1..n-1] connect properly. A mistake in handling the edge when the subarray is at the beginning or end (or empty) could lead to errors.
- Using < instead of <=: Since the array needs to be non-decreasing (allowing equal elements), make sure to use <= when checking sorted order. Using < would misidentify valid sorted sequences that contain equal elements.

Edge Cases to Consider:

Already Sorted Array: As discussed, if the array is already sorted (e.g., [1,2,3,4] or all elements equal like [7,7,7]), the answer should be 0 (remove nothing). Make sure your code checks for this explicitly or implicitly.
Strictly Decreasing Array: If every element is smaller than the previous (e.g., [5,4,3,2,1]), you can only leave one element. The answer should be n-1 because you must remove everything except one element (any single element is trivially sorted by itself).
All Equal Elements: If arr = [k, k, k, ..., k], the array is already non-decreasing (all elements are equal), so the answer is 0. Both the prefix and suffix in this case would extend over the entire array.
Small Arrays: For an array of length 1, the answer is 0 (already sorted). For length 2, the answer is 0 if they’re in order or 1 if they’re decreasing (remove one of them).
Prefix or Suffix covers the array: It’s possible that the longest sorted prefix goes almost to the end or the longest sorted suffix goes almost to the beginning. For example, arr = [1,2,3,4,0] has a prefix sorted till index 3 and suffix from index 4. Here you could either remove the single out-of-order element 0 (suffix case) or everything after 4 (prefix case). The algorithm handles this by considering removing after prefix or before suffix initially, and then checking combinations.

Alternate Variations of the Problem:

A related problem is “Shortest Unsorted Continuous Subarray” (LeetCode 581). In that problem, you need to find the shortest subarray which, if sorted, would make the whole array sorted. It sounds similar but is different: you are sorting that subarray in place, not removing it. The approach to that problem is different (finding boundaries of the unsorted portion by comparing with sorted versions of the array, etc.).
Another variation is: “Remove at most one element to make array sorted.” That is a simpler special case of this problem where the subarray to remove is of size at most 1. It can be solved with a simple one-pass check or two.
A more general problem is: “Minimum removals to make an array sorted (not necessarily contiguous).” If you were allowed to remove any elements (not necessarily a single contiguous block), the problem becomes finding the longest increasing subsequence (LIS) and removing everything else. That’s a different scenario because you could take out scattered elements. Our problem is stricter since the removals have to be one consecutive segment.
“Merge two sorted subarrays” type problems or “check if array can be split into two sorted parts” are conceptually related in that they deal with maintaining sorted order across boundaries, similar to how we handle prefix and suffix here.

1574. Shortest Subarray to be Removed to Make Array Sorted - Detailed Explanation

Problem Statement:

Hints Section:

Approaches:

Step-by-Step Walkthrough:

Additional Insights:

Edge Cases to Consider:

Alternate Variations of the Problem:

Related Problems for Practice: