Shortest Cut to Sort
HardTwo Pointers
Problem
A playlist stores track tempos in arr. You may delete one contiguous block of tracks (possibly empty) so that the remaining tracks, kept in their original order, are in non-decreasing tempo order.
Return the length of the shortest block you must delete.
Example 1
- Input:
- arr = [1, 2, 8, 3, 4, 2, 6]
- Output:
- 3
Delete [8, 3, 4] (indices 2–4) to keep [1, 2, 2, 6], which is sorted. No block of length 2 or less works.
Example 2
- Input:
- arr = [1, 2, 3]
- Output:
- 0
Already sorted.
Example 3
- Input:
- arr = [5, 4, 3, 2]
- Output:
- 3
Only one track can stay.
Constraints
- 1 ≤ arr.length ≤ 10^5
- 0 ≤ arr[i] ≤ 10^9
Hint
Show the first hint
What remains after the cut is a prefix plus a suffix. Each must be sorted on its own.
Walkthrough
How to approach it
01Clarify before coding
- Must the deleted block be contiguous? Yes, exactly one block (possibly empty).
- Is non-decreasing enough, or strictly increasing? Non-decreasing: equal neighbours are fine.
- Can everything except one element be deleted? Yes, a single element is sorted.
02Brute force
Try every block [i, j), delete it and check whether the rest is sorted.
Cost: O(n³) naively, O(n²) with precomputed sorted-prefix/suffix flags: too slow for n = 10^5.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.