Shortest Unsorted Continuous Subarray
Medium · Arrays & Hashing · Array · Two Pointers · Stack · Greedy · Sorting · Monotonic Stack
Problem
You are given an integer array nums. Find the shortest contiguous subarray such that sorting only that subarray in ascending order makes the whole array sorted in ascending order.
Return the length of that subarray. If the array is already sorted, return 0.
Examples
Input: nums = [2,6,4,8,10,9,15] Output: 5
Sorting [6,4,8,10,9] (indices 1 to 5) sorts the whole array.
Input: nums = [1,2,3,4] Output: 0
Nothing needs to move.
Input: nums = [1,3,7,4,5,2,9] Output: 5
The 2 at index 5 belongs after the 1, so the window runs from index 1 to index 5.
Constraints
- 1 <= len(nums) <= 10^4
- -10^5 <= nums[i] <= 10^5
Approaches
- Compare with a sorted copy — time O(n log n), space O(n)
Follow-up
Can you do it in one pass? Run both scans in the same loop with i from the left and n - 1 - i from the right. And if you had to report the window itself, return [start, end] instead of its length; the scans already find both ends.
Related problems
Start free on Cariara · Coding problems · System design studio
