Shortest Unsorted Continuous Subarray
mediumTime: O(n)Space: O(1)
Recognize the pattern
shortest subarray to sort so whole array is sortedfind out-of-order boundariesrunning max/min scan
Brute force idea
Sort and compare — O(n log n).
Better approach
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).
Key invariant
Right boundary = rightmost element smaller than some element to its left. Left boundary = leftmost element larger than some element to its right.
Watch out for
Only finding first violation — the unsorted region may extend beyond the first break.