Space
Open
From Fieldwork
Scales
Archive
This is actually mostly an index hygiene question.
Bounds check first, value check second.
We have to calculate the "elements removed" with a - 1 because we don't want to count the destination.
We're looking for the open interval. Therefore, we need to take off the destination.
This... goes pretty deep. I'm not even talking about the algorithm here, which is just a kind of the merge of merge sort, which is just comparing numbers.
This stuff with the indexing actually gets into the difference between Cardinals (counts) and Ordinals (positions).
Subtraction calculates displacement. Likewise, 0-based indexing implies displacement from the start.
Because the index is the distance, subtraction works well for Half-Open intervals (include Start, Exclude end, or vice versa).
https://aistudio.google.com/prompts/1TgZSYezFfwkXV1mgbMPM5fVqdIzXIt2p
class Solution:
def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
n = len(arr)
# 1. Find the longest non-decreasing prefix (left portion)
left = 0
while left < n - 1 and arr[left] <= arr[left + 1]:
left += 1
# Postcondition: left marks the inclusive end of the leftmost sorted portion
# If the whole array is sorted:
if left == n - 1:
return 0
# 2. Find the longest non-decreasing suffix (right portion)
right = n - 1
while right > 0 and arr[right - 1] <= arr[right]:
right -= 1
# 3. Initial answer: remove either all prefix or all suffix
# Removing everything after arr[left] (length = n - 1 - left)
# Removing everything before arr[right] (length = right)
result = min(n - left - 1, right)
# 4. Use two pointers to merge prefix and suffix
i = 0
j = right
while i <= left and j < n:
if arr[i] <= arr[j]:
# Valid merge: we keep arr[0..i] and arr[j..n-1]
# Elements removed are between i and j
# Count = j - i - 1
result = min(result, j - i - 1)
i += 1
else:
# arr[i] is too big; we need a larger element from the right side
j += 1
return result
Practice bench
A private scratchpad for this reading. Nothing is sent or scored.
What is still unclear, or what would change the explanation?
Saved on this device · one draft per mode