399. Shortest Unsorted Window
A warehouse has a row of crates tagged with weights, and the row is supposed to be arranged from the lightest to the heaviest (equal weights may sit side by side). The row got shuffled in one place only, and a worker will fix it by picking one unbroken stretch of crates and reordering just that stretch.
Given the array nums of weights, return the length of the shortest contiguous stretch that, once sorted in non-decreasing order, leaves the entire row sorted. If the row is already in order, return 0. Sorting the whole array and comparing is easy, but the row can be very long, so aim for a linear scan.
Example 1
- Input:
- nums = [14,20,31,27,22,40,52]
- Output:
- 3
- Explanation:
Only the stretch 31, 27, 22 is out of place together with 20 (which must move after 22) and 27: sorting positions 1 to 4 gives 14, 20, 22, 27, 31, 40, 52, so the length is 4.
Example 2
- Input:
- nums = [-8,-8,3,3,9,9]
- Output:
- 0
- Explanation:
The row is already non-decreasing, so no stretch needs sorting.
Constraints
1 ≤ nums.length ≤ 105
-105 ≤ nums[i] ≤ 105
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)