Shortest Unsorted Continuous Subarray
mediumTime: 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).
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.
Easy way to go wrong
Only finding first violation — the unsorted region may extend beyond the first break.