FunctionRacerProblemsRace

Shortest Cut That Leaves It Sorted

MediumTwo pointersPython, JavaScript, TypeScript, Java, C++

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

nums [1,2,3,10,4,2,3,5]
returns 3

Cutting out [10, 4, 2] leaves [1, 2, 3, 3, 5], which is sorted; no shorter block works.

Example 2

nums [5,4,3,2,1]
returns 4

Every block shorter than 4 leaves two items out of order, so 4 items must go, leaving a single item.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Two pointers problems