Problem Statement

Shortest Unsorted Continuous Subarray

You are given an array of numbers. Most of it might already be in sorted order, but one chunk in the middle could be jumbled. Your job is to find the shortest stretch of the array that you could pull out, sort on its own, and drop back in, so that the whole array ends up sorted. The answer is the length of that stretch. To do this we hunt for two things: the leftmost spot where the order breaks, and the rightmost spot where the order breaks. The trick that makes this fast is a "running max" and a "running min". A running max is just the biggest number you have seen so far as you walk along. A running min is the smallest number you have seen so far. Here is the idea, said plainly. If you walk left to right and you ever see a number that is smaller than the biggest number behind it, that number is in the wrong place, so the messy region must reach at least this far right. If you walk right to left and you ever see a number that is bigger than the smallest number ahead of it, that number is in the wrong place too, so the messy region must reach at least this far left.

mediumArrayStackStackTime: O(n) · Space: O(1)

Signals to notice

shortest subarray to sort so whole array is sortedfind out-of-order boundariesrunning max/min scan

Brute force first

Sort and compare — O(n log n).

The key insight

Left-to-right: track running max. Any element < max is out of order (right boundary). Right-to-left: track running min. Any element > min (left boundary). O(n).

Trace it on `nums=[2,6,4,8,10,9,15]`

Pass 1 (L->R, track max, set right). i=0 v=2: max=2. i=1 v=6: max=6.
i=2 v=4 < max6 -> right=2. i=3 v=8: max=8. i=4 v=10: max=10.
i=5 v=9 < max10 -> right=5. i=6 v=15: max=15. End pass 1: right=5.
Pass 2 (R->L, track min, set left). i=6 v=15: min=15. i=5 v=9: min=9.
i=4 v=10 > min9 -> left=4. i=3 v=8: min=8. i=2 v=4: min=4.
i=1 v=6 > min4 -> left=1. i=0 v=2: min=2. End pass 2: left=1.
right(5) != -1, so answer = right - left + 1 = 5 - 1 + 1 = 5.
Return 5 (sort nums[1..5] -> [2,4,6,8,9,10,15] is fully sorted).

What must stay true

Right boundary = rightmost element smaller than some element to its left. Left boundary = leftmost element larger than some element to its right.

Shape of the loop

right = -1; maxVal = -inf
for i in 0..n-1:        # left-to-right finds right boundary
    if nums[i] < maxVal: right = i
    maxVal = max(maxVal, nums[i])
left = 0; minVal = +inf
for i in n-1..0:        # right-to-left finds left boundary
    if nums[i] > minVal: left = i
    minVal = min(minVal, nums[i])
return right == -1 ? 0 : right - left + 1

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Only finding first violation — the unsorted region may extend beyond the first break.

Stack Pattern