Show problems as
Classic problem #1574MediumArrayTwo PointersBinary SearchStackMonotonic Stack

Shortest Subarray to be Removed to Make Array Sorted

Real-world version: Cutting One Stretch to Leave the Gauges Rising
Tracked in this browser only
Read Shortest Subarray to be Removed to Make Array Sorted on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A rail of gauges reads gauges. Remove exactly one stretch of neighbouring gauges, possibly an empty one, so that what is left, read in order, never falls: every remaining reading is at least the one before it.

Return the length of the shortest stretch that can be removed. Removing nothing counts, and so does removing all but one reading.

Examples

Example 1

Input
gauges = [1, 2, 3, 10, 4, 2, 3, 5]
Output
3

The rail rises through 1, 2, 3 at the front and through 3, 5 at the back. Dropping the three readings 10, 4 and 2 that lie between them leaves 1, 2, 3, 3, 5, which never falls, and no shorter cut manages it.

Example 2

Input
gauges = [5, 4, 3, 2, 1]
Output
4

The rail falls at every step, so no two readings can survive together and four of the five have to go.

Example 3

Input
gauges = [1, 2, 3, 0, 4, 5]
Output
1

Only the single 0 is out of place; dropping it leaves 1, 2, 3, 4, 5.

Constraints

  • 1 <= gauges.length <= 10^5
  • 0 <= gauges[i] <= 10^9

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def find_length_of_shortest_subarray(gauges: list[int]) -> int:
Java
public int findLengthOfShortestSubarray(int[] gauges)

More on the same topics