Shortest Unsorted Continuous Subarray
Solve and submit on LeetCode to build your LeetCode profile. Use the hints here when you need guidance.
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)
