1679. Shortest Subarray to be Removed to Make Array Sorted
My accepted Python solution to LeetCode problem 1679, Shortest Subarray to be Removed to Make Array Sorted, running in 13ms.
- Difficulty: Medium
- Python
- Runtime 13ms
- Memory 32MB
- Updated
Read the problem on LeetCode View on GitHub
The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.
Python
Accepted on LeetCode — runtime 13ms, memory 32MB, accepted 2025-12-29.
class Solution:
def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
# Find longest non-decreasing prefix and suffix
# Then try to merge them optimally
# Time: O(n), Space: O(1)
n = len(arr)
# Find rightmost point of non-decreasing prefix
left = 0
while left < n - 1 and arr[left] <= arr[left + 1]:
left += 1
# Already sorted
if left == n - 1:
return 0
# Find leftmost point of non-decreasing suffix
right = n - 1
while right > 0 and arr[right - 1] <= arr[right]:
right -= 1
# Option 1: Remove everything after prefix
# Option 2: Remove everything before suffix
result = min(n - left - 1, right)
# Option 3: Merge prefix and suffix
i, j = 0, 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