DSA problem
Shortest Unsorted Continuous Subarray
Given an integer array nums, find one continuous subarray such that if you sort only that subarray in non-decreasing order, the entire array becomes sorted in non-decreasing order. Return the length of the shortest such subarray. If the array is already sorted, return 0.
A clean characterisation: define left as the smallest index where nums[left] violates non-decreasing order with respect to the prefix max, and right as the largest index where nums[right] violates non-decreasing order with respect to the suffix min. The answer is max(0, right - left + 1).
A two-pass scan implements this directly: scan left-to-right tracking the running max — every time nums[i] < runningMax, update right = i. Scan right-to-left tracking the running min — every time nums[i] > runningMin, update left = i. The window [left, right] is the answer.
Equivalently, two monotonic stacks identify the same boundaries: a monotonic increasing stack going left-to-right finds the earliest dip from a peak (left boundary); a monotonic decreasing stack going right-to-left finds the latest dip from a trough (right boundary). Both views run in O(n) time and O(1) extra space for the running-max/min version.
Examples
nums = [2,6,4,8,10,9,15]5nums = [1,2,3,4]0nums = [1]0Constraints
- 1 <= nums.length <= 10^4
- -10^5 <= nums[i] <= 10^5
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.