Shortest Subarray to be Removed to Make Array Sorted

LeetCode Shortest Subarray to be Removed to Make Array Sorted (problem 1574) asks you to find the length of the shortest contiguous subarray you can remove so the remaining elements form a non-decreasing sequence.

The problem

Given an integer array arr, remove one contiguous subarray (possibly empty) so that the remaining elements are sorted in non-decreasing order. Return the minimum length of the subarray to remove.

Example: arr = [1, 2, 3, 10, 4, 2, 3, 5]. Remove the subarray [10, 4, 2] at indices 3 through 5. The remaining array [1, 2, 3, 3, 5] is sorted. The answer is 3.

The brute force approach

You could try every possible subarray to remove: for each pair of indices (i, j), check whether deleting arr[i..j] leaves a sorted array. That is O(n^3) in the worst case, O(n^2) pairs each requiring an O(n) check. Far too slow for arrays up to length 100,000.

The key insight

The array already has a sorted prefix on the left and a sorted suffix on the right. You only need to remove a contiguous chunk from the middle. The trick is figuring out how much of the prefix and suffix you can keep while ensuring the last element of the kept prefix is less than or equal to the first element of the kept suffix.

Step-by-step walkthrough

Here is the approach:

1. Find the sorted prefix. Scan from the left while arr[i] <= arr[i + 1]. Call the last index of this prefix left.
2. Check if already sorted. If left reaches the end, the array is already sorted. Return 0.
3. Find the sorted suffix. Scan from the right while arr[j - 1] <= arr[j]. Call the first index of this suffix right.
4. Baseline candidates. You can remove everything after the prefix (cost n - left - 1) or everything before the suffix (cost right). Take the minimum of these two as your starting answer.
5. Two-pointer merge. Walk i through the prefix (0 to left) and for each i, advance right until arr[i] <= arr[right]. The removal cost for that pair is right - i - 1. Track the minimum across all valid pairs.

The two-pointer pass works because both the prefix and suffix are individually sorted. As i increases, arr[i] can only grow, so right never needs to move backwards.

The code

def findLengthOfShortestSubarray(arr):
    n = len(arr)
    left = 0
    while left < n - 1 and arr[left] <= arr[left + 1]:
        left += 1

    if left == n - 1:
        return 0

    right = n - 1
    while right > 0 and arr[right - 1] <= arr[right]:
        right -= 1

    result = min(n - left - 1, right)

    i = 0
    j = 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

The first loop finds the longest non-decreasing prefix. If it spans the whole array, we return 0 immediately. The second loop finds the longest non-decreasing suffix. The initial result considers removing everything after the prefix or everything before the suffix. Then the two-pointer loop tries to stitch together a portion of the prefix with a portion of the suffix, tracking the smallest gap between them.

Complexity analysis

Each of the three scans (prefix, suffix, two-pointer merge) visits each element at most once. The total work is linear. No extra data structures are needed beyond a few integer variables.

The building blocks

Sorted prefix and suffix identification

Many array problems start by identifying how much of the array is already in order. You scan from the left to find where the sorted prefix ends, and from the right to find where the sorted suffix begins. This same technique appears in problems like checking if an array is "almost sorted" or finding the minimum window to sort.

Two-pointer merge on sorted segments

Once you have two sorted segments (the prefix and the suffix), you use two pointers to find the best way to join them. Pointer i walks the prefix and pointer j walks the suffix. Because both segments are sorted, j only moves forward, giving you O(n) total work. This is the same idea behind merging two sorted arrays, just applied to finding a compatible junction point.

Binary search alternative

Instead of the two-pointer merge, you could binary search for each prefix element: for a given arr[i], find the leftmost position in the suffix where arr[j] >= arr[i]. This also runs in O(n log n) and is a valid approach, though the two-pointer version is simpler and faster in practice.

Edge cases

• Already sorted array: the prefix spans the entire array. Return 0.
• Completely unsorted (strictly decreasing): the prefix is just the first element and the suffix is just the last element. You may need to remove n - 1 or n - 2 elements.
• Single element: always sorted. Return 0.
• Remove from the front only: when the suffix starts early and no prefix element fits, the answer is right (remove everything before the suffix).
• Remove from the end only: when the prefix extends far and no suffix element connects, the answer is n - left - 1.
• All elements equal: the entire array is non-decreasing. Return 0.

From understanding to recall

The core idea here, finding sorted ends and stitching them together, is easy to understand when you see it drawn out. But the details trip people up in practice. Where does left stop? Where does right start? What are the initial candidates for result? Which pointer advances in the merge loop?

Those details solidify through repetition. Trace through [1, 2, 3, 10, 4, 2, 3, 5] by hand. Then try [5, 4, 3, 2, 1]. Then try [1, 2, 3]. Each repetition cements the logic a little deeper. After a few spaced practice sessions, you will not need to re-derive the algorithm. The pattern of "find the sorted ends, merge with two pointers" will feel automatic.

Related posts

• Remove Duplicates from Sorted Array - Another problem that leverages sorted-order structure with a two-pointer technique to modify an array in place.
• Merge Sorted Array - The classic two-pointer merge on sorted sequences, which is the same core mechanic used in the merge step of this problem.
• Longest Increasing Subsequence - A different angle on finding ordered structure within an array, using dynamic programming instead of removal.