Shortest Cut That Leaves It Sorted
You may cut one contiguous block out of nums and discard it; the items before and after the block close up in their original order. Return the length of the shortest block whose removal leaves the remaining items in non-decreasing order. Cutting nothing is allowed, so a list that is already non-decreasing gives 0, and the remaining part may be empty.
What remains is a non-decreasing prefix of nums joined to a non-decreasing suffix whose first item is at least the prefix's last item. Find the longest non-decreasing prefix and the longest non-decreasing suffix, then slide one index over each to pair them up.
Example 1
Cutting out [10, 4, 2] leaves [1, 2, 3, 3, 5], which is sorted; no shorter block works.
Example 2
Every block shorter than 4 leaves two items out of order, so 4 items must go, leaving a single item.
Constraints
1 <= len(nums) <= 100-1000 <= nums[i] <= 1000
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Two pointers problems
- Shortest Stretch With Every Required LetterMedium
- Sort ColorsMedium
- Stretches With a Sum in RangeMedium
- Subarrays With Small ProductMedium
- Three SumMedium
- Trim Both Ends to a TotalMedium
- Valid Palindrome IIMedium
- Valid Triangle NumberMedium