Shortest Unsorted Continuous Subarray
Problem
Find the shortest contiguous subarray which, if sorted by itself, would make the whole array sorted in ascending order. Return its length, or 0 if the array is already sorted.
Examples
Constraints
- • 1 <= nums.length <= 10^4
- • -10^5 <= nums[i] <= 10^5
Hints & approach
Hint 1
Comparing with a sorted copy gives an O(n log n) answer. Can you avoid sorting?
Hint 2
Scanning left to right, any element smaller than the running maximum is out of place.
Hint 3
Symmetrically, scanning right to left, any element larger than the running minimum is out of place.
Approachtry the hints first
Sweep left to right keeping the running maximum; the last index whose value is below that maximum is the right boundary. Sweep right to left keeping the running minimum; the last index whose value is above that minimum is the left boundary. If no boundary was found the array is sorted and the answer is 0; otherwise it is right - left + 1.
Time O(n) · Space O(1)