Show problems as
Classic problem #581MediumArrayTwo PointersStackGreedySortingMonotonic Stack

Shortest Unsorted Continuous Subarray

Real-world version: Shortest Stretch to Re-sort
Tracked in this browser only
Read Shortest Unsorted Continuous Subarray on LeetCode(opens in a new tab)

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

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

More on the same topics