658. The Shortest Piece to Cut Out
Remove ONE contiguous piece from the array, possibly empty, so that what remains is non-decreasing. Print the shortest length that can be removed.
1 2 3 10 4 2 3 5 -> 3 removing 10 4 2
5 4 3 2 1 -> 4
1 2 3 -> 0 already sorted
## The shape of the answer
Whatever is removed, what remains is a PREFIX followed by a SUFFIX. So the surviving prefix must be non-decreasing, the surviving suffix must be non-decreasing, and the join between them must not step down.
Find the longest non-decreasing prefix, ending at left, and the longest non-decreasing
suffix, starting at right. Nothing outside those can survive, so those two are the only
candidates to draw from.
## The three ways to answer
keep the prefix only: remove n - left - 1
keep the suffix only: remove right
keep both: for each i in the prefix, find the earliest j in the suffix
with a[i] <= a[j], and remove j - i - 1
If the prefix already reaches the end, the array is sorted and the answer is 0.
## The joining sweep
i = 0, j = right
while i <= left and j < n:
if a[i] <= a[j]: best = min(best, j - i - 1); i += 1
else: j += 1
Both cursors move forward only. When a[i] <= a[j] the join is legal, the gap is recorded, and
a LARGER i can only do better, so i advances. When the join is illegal, a[i] needs a
larger partner, so j advances.
That is the same reasoning as problem 632, where both pointers also move forward because the question is about matching rather than about a total.
## Why the prefix-only and suffix-only cases must be included
The sweep only considers joins that actually happen. If no prefix value can be joined to any suffix value, the loop records nothing, and the answer is one of the two one-sided removals.
5 4 3 2 1 is the case: the prefix is just 5, the suffix just 1, and 5 <= 1 is false, so
the sweep records nothing and the answer is 4.
## Boundaries
An already sorted array answers 0 and must not fall through into the sweep. A single value answers 0.
## Cost
Time O(n). Space O(1).
Constraints - `1 ≤ n ≤ 200000` - `-10^9 ≤ each value ≤ 10^9`
Input
The first line contains an integer n.
The second line contains n integers.
Output
Print one integer, the shortest length that can be removed.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.