1006MediumArrayTwo PointersBinary SearchStackMonotonic Stack

Cutting One Stretch to Leave the Gauges Rising

Tracked in this browser only

Trains the technique from

LeetCode 1574Shortest Subarray to be Removed to Make Array Sorted

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def find_length_of_shortest_subarray(gauges: list[int]) -> int:

Java

public int findLengthOfShortestSubarray(int[] gauges)

The intended approach

Time O(n) over the rail's length.Space O(1).

Whatever stretch comes out, what is left is a piece from the front of the rail joined to a piece from the back. So start by measuring how far the rail rises from the left before it first falls, and how far it rises reading backwards from the right end. Those two runs are the largest front and back pieces that could ever survive. If the front run already reaches the far end, the rail never falls and nothing needs removing. Otherwise two easy candidates are keeping the whole front run and dropping the rest, or keeping the whole back run and dropping the rest. Anything better joins a front piece to a back piece. Walk the front piece's last reading forward through the front run. For each one, the earliest place the back piece may begin is the first reading in the back run that is at least as large. Since the front piece's last reading only grows as the piece lengthens, that earliest place only moves forward too, so one pointer crosses the back run once for the whole walk. Each pairing removes everything lying between, and the smallest such gap is the answer.

Pythonentry point: find_length_of_shortest_subarray

def find_length_of_shortest_subarray(gauges):
    n = len(gauges)
    left = 0
    while left + 1 < n and gauges[left + 1] >= gauges[left]:
        left += 1
    if left == n - 1:
        return 0
    right = n - 1
    while right > 0 and gauges[right - 1] <= gauges[right]:
        right -= 1
    best = n - left - 1
    if right < best:
        best = right
    front = 0
    back = right
    while front <= left and back < n:
        if gauges[back] >= gauges[front]:
            gap = back - front - 1
            if gap < best:
                best = gap
            front += 1
        else:
            back += 1
    return best

The obvious version

Try the removals by length, shortest first, and for each length try every starting place, gluing the two remaining pieces together and walking the result to see whether it ever falls. The first length that works is the answer. Costs every removal times the rail's length rather than two runs and a single pointer sweep.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_find_length_of_shortest_subarray(gauges):
    n = len(gauges)
    def rises(part):
        for at in range(1, len(part)):
            if part[at] < part[at - 1]:
                return False
        return True
    for length in range(n + 1):
        for start in range(n - length + 1):
            if rises(gauges[:start] + gauges[start + length:]):
                return length
    return n

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in