⚡Flashcard Drill➔
NeetCode #816LC-1574MediumGreedy
← Back to All Problems

#816 · #1574 · Shortest Subarray to be Removed to Make Array Sorted(删除最短的子数组使剩余数组有序)

📌 Problem Statement & Constraints

Given an integer array arr, you may remove one contiguous subarray so that the remaining elements are non-decreasing. Return the minimum length of such a subarray. Constraints: 1 <= arr.length <= 10^5, 0 <= arr[i] <= 10^9.

💡 Core Algorithmic Approaches

  1. The longest non-decreasing prefix [0, r] and the longest non-decreasing suffix [l, n-1] are both easy to find by scanning.
  2. Removing everything after the prefix costs n - r - 1; removing everything before the suffix costs l.
  3. The third option is to keep a prefix and a suffix and remove the middle, so the two kept parts must join: arr[i] <= arr[j].
  4. Two pointers i over the prefix and j over the suffix find the best join, and the answer is the minimum over all three options.

💻 Benchmark Python3 Implementation

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n = len(arr)
        r = 0
        while r + 1 < n and arr[r] <= arr[r + 1]:   # longest non-decreasing prefix
            r += 1
        if r == n - 1:
            return 0                                # already sorted
        l = n - 1
        while l - 1 >= 0 and arr[l - 1] <= arr[l]:  # longest non-decreasing suffix
            l -= 1
        ans = min(n - r - 1, l)                     # drop one side entirely
        i, j = 0, l
        while i <= r and j < n:
            if arr[i] <= arr[j]:                    # keep prefix up to i and suffix from j
                ans = min(ans, j - i - 1)
                i += 1
            else:
                j += 1
        return ans

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): the two boundary scans and the merge are each linear.
💾 Space Complexity
O(1): a few indices.

⚠️ Interview Pitfalls & Follow-ups

  • Assuming the removed part is always a middle chunk: removing a prefix or a suffix can also be optimal, which the min(n - r - 1, l) term covers.
  • Comparing with strict inequality: the array must be non-decreasing, so arr[i] <= arr[j] is the correct join test.
  • Advancing both pointers on a valid join: only i should advance after a successful join, since j may still pair with a larger i.
  • Forgetting the already-sorted case: without the early return, the pointer logic can underflow; r == n - 1 means no removal is needed.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems