421. Shortest Unsorted Continuous Subarray
You're given an integer array nums. Find the shortest contiguous subarray with this property: sort just that subarray in non-decreasing order, and the whole of nums becomes sorted in non-decreasing order.
Return the length of that subarray.
If nums is already sorted (equal neighbors are fine), nothing needs sorting — return 0.
Example 1:
Input: nums = [2, 6, 4, 8, 10, 9, 15]
Output: 5
Explanation: Sorting the middle block [6, 4, 8, 10, 9] (indices 1 through 5) yields [2, 4, 6, 8, 9, 10, 15], which is fully sorted. No shorter block works.
Example 2:
Input: nums = [1, 2, 3, 4]
Output: 0
Explanation: The array is already in non-decreasing order, so the empty subarray suffices.
Example 3:
Input: nums = [1, 3, 2, 2, 2]
Output: 4
Explanation: Sorted, the array is [1, 2, 2, 2, 3]: positions 1 through 4 all change, so the block [3, 2, 2, 2] of length 4 must be sorted — duplicates drag the window wider than it first looks.
Constraints:
- 1 ≤ nums.length ≤ 10⁵
- -10⁵ ≤ nums[i] ≤ 10⁵
- nums may contain duplicates; sorted means non-decreasing
Hints:
Sort a copy and compare it with the original. The first and last positions where the two disagree bracket exactly the region that has to move — everything outside is already in its final place.
For O(n) without sorting: sweep left to right carrying a running maximum — the last index whose value dips below that maximum is the window's right edge. Mirror the sweep from the right with a running minimum to find the left edge.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [2, 6, 4, 8, 10, 9, 15]
Expected output: 5