0582MediumArrayTwo PointersStackGreedySortingMonotonic Stack

Shortest Stretch to Re-sort

Tracked in this browser only

Trains the technique from

LeetCode 581Shortest Unsorted Continuous Subarray

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 conveyor presents parts in the order given by nums, where nums[i] is the signed weight offset of the part in slot i. Offsets may be negative and two parts may share an offset.

An operator may pick out one unbroken stretch of slots, sort the parts inside it into non-decreasing order of offset, and put them back into the same slots. The goal is for the whole line, read from slot 0 to the last slot, to end up non-decreasing.

Return the length of the shortest stretch that achieves this. If the line is already non-decreasing, return 0.

Examples

Example 1

Input: nums = [1, 3, 5, 4, 2, 6]
Output: 4

Sorting slots 1 through 4, which hold 3, 5, 4 and 2, puts 2, 3, 4, 5 there and the line reads 1, 2, 3, 4, 5, 6. That stretch is four slots long, and no stretch of three or fewer slots leaves the line non-decreasing.

Example 2

Input: nums = [4, 4, 6, 8, 8]
Output: 0

Every slot already holds an offset at least as large as the one before it, so nothing has to be picked out.

Example 3

Input: nums = [-5, -5, -6, 4, 10, 10, 9]
Output: 7

Slot 2 holds -6, which has to move ahead of both -5s, and slot 6 holds 9, which has to move ahead of both 10s, so the stretch runs from slot 0 to slot 6 and covers all seven slots.

Constraints

1 <= nums.length <= 10^4
-10^5 <= nums[i] <= 10^5

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_unsorted_subarray(nums: list[int]) -> int:

Java

public int findUnsortedSubarray(int[] nums)

The intended approach

Time O(n) — two sweeps of the line.Space O(1) — four scalars.

A slot belongs inside the stretch when some part that must finish ahead of it currently sits behind it. Sweep from the left carrying the tallest offset seen so far: every slot holding less than that tallest offset is out of place, and the last one of those is the right edge. Sweep from the right carrying the lightest offset seen from that side: every slot holding more than it is out of place, and the first one of those is the left edge. If the left sweep never flags a slot, the line is already in order.

Pythonentry point: find_unsorted_subarray

def find_unsorted_subarray(nums):
    # O(n) time, O(1) space: sweeping left to right, any entry below the tallest
    # weight seen so far has to end up inside the stretch, so the last such
    # entry fixes the right edge. Sweeping right to left, any entry above the
    # lightest weight seen from that side fixes the left edge.
    n = len(nums)
    right = -1
    tallest = nums[0]
    for i in range(1, n):
        if nums[i] < tallest:
            right = i
        elif nums[i] > tallest:
            tallest = nums[i]
    if right == -1:
        return 0
    left = n
    lightest = nums[n - 1]
    for i in range(n - 2, -1, -1):
        if nums[i] > lightest:
            left = i
        elif nums[i] < lightest:
            lightest = nums[i]
    return right - left + 1

The obvious version

Sort a copy of the line. Walk in from both ends comparing the line with the sorted copy slot by slot; the first and last slots that disagree bound the stretch. Full agreement means the line was already in order.

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_unsorted_subarray(nums):
    target = sorted(nums)
    n = len(nums)
    lo = 0
    while lo < n and nums[lo] == target[lo]:
        lo += 1
    if lo == n:
        return 0
    hi = n - 1
    while nums[hi] == target[hi]:
        hi -= 1
    return hi - lo + 1

How this problem was checked

Reference solution executed against 11 test cases — 11 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