Shortest Unsorted Continuous Subarray in O(N) Time
Given an integer array
nums, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order.
Return the shortest such subarray and output its length.
Consider the case
nums = [1, 5, 2, -1, 7]
- Find the first element that is out of order from the left.
5is the one out of order because it is larger than
2. The number should keep increasing as we move to the right.
- Find the last element that is out of order from the right.
-1is the one out of order because it is smaller than
2. The number should keep decreasing as we move to the left.
- After Step 1 and 2, we will get the initial window/subarray (
[5, 2, -1]). However, we will not get a sorted array by just sorting this 3 elements. We need to include the first element,
[-1, 1, 2, 5, 7]is the correct sorted array.
- So we need to expand our window to the left to include more elements if our initial subarray contains a number that is smaller than the number outside the window on the left. For example, we need to include
1at index 0 because it is larger than
-1which exists in our initial window.
- Do the same for the right side. If the initial subarray contains a number that is larger than the number outside the window on the right.
- For this example,
[1, 5, 2, -1] => Length = 4is the correct answer to our problem
Time and Space Complexity
We look through the array only once, so the algorithm is O(N).
The algorithm runs in constant space O(1).