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
- The longest non-decreasing prefix
[0, r]and the longest non-decreasing suffix[l, n-1]are both easy to find by scanning. - Removing everything after the prefix costs
n - r - 1; removing everything before the suffix costsl. - 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]. - Two pointers
iover the prefix andjover 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
ishould advance after a successful join, sincejmay still pair with a largeri. - Forgetting the already-sorted case: without the early return, the pointer logic can underflow;
r == n - 1means 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.