Shortest Unsorted Continuous Subarray
01 · Problem
Given an integer array nums, find one contiguous 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 nums is already sorted, return 0. Non-decreasing order means equal adjacent values are allowed.
02 · Examples
nums = [2,6,4,8,10,9,15]
5
Sorting the slice [6,4,8,10,9] (indices 1 to 5) gives [2,4,6,8,9,10,15]. No shorter slice works, so the answer is 5.
nums = [1,2,3,4]
0
The array is already sorted, so nothing needs to be sorted.
nums = [1,3,2,2,2]
4
Sorting indices 1 to 4 ([3,2,2,2]) gives [1,2,2,2,3]. Equal values count as sorted, but the 3 must move past all the 2s.
03 · Constraints
- 011 <= nums.length <= 104
- 02-105 <= nums[i] <= 105
- 03The answer is between 0 and nums.length
04 · Optimal complexity
- Time
- O(n)
- Space
- O(1)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.