Shortest Unsorted Continuous Subarray
Medium · Two Pointers · Explanation and code example
Find the Disorder Extremes and Expand Bounds
How it works
After the first decrease from the left, record the minimum of the remaining suffix. After the first increase while scanning backward, record the maximum of the earlier prefix. Values outside the disorder range that exceed that minimum or fall below that maximum must be included in the sorted interval.
Steps
- Find the minimum after a left-to-right inversion.
- Find the maximum after a right-to-left inversion.
- Locate the first value above the minimum and the last below the maximum.
Complexity
- Time: O(n).
- Space: O(1) for scans in the adapted examples.
Things to watch for
- An already sorted array returns zero.
- Repeated equal values alone are not inversions.
- The interval can extend beyond the initially adjacent inversion.
Python code example
import math
class Solution:
def findUnsortedSubarray(self, nums: list[int]) -> int:
mn = math.inf
mx = -math.inf
flag = False
for i in range(1, len(nums)):
if nums[i] < nums[i - 1]:
flag = True
if flag:
mn = min(mn, nums[i])
flag = False
for i in reversed(range(len(nums) - 1)):
if nums[i] > nums[i + 1]:
flag = True
if flag:
mx = max(mx, nums[i])
for l in range(len(nums)):
if nums[l] > mn:
break
for r, num in ((i, nums[i]) for i in range(len(nums) - 1, -1, -1)):
if num < mx:
break
return 0 if l >= r else r - l + 1
C++ code example
class Solution {
public:
int findUnsortedSubarray(vector<int>& nums) {
const int n = nums.size();
int mn = INT_MAX;
int mx = INT_MIN;
bool meetDecrease = false;
bool meetIncrease = false;
for (int i = 1; i < n; ++i) {
if (nums[i] < nums[i - 1])
meetDecrease = true;
if (meetDecrease)
mn = min(mn, nums[i]);
}
for (int i = n - 2; i >= 0; --i) {
if (nums[i] > nums[i + 1])
meetIncrease = true;
if (meetIncrease)
mx = max(mx, nums[i]);
}
int l;
for (l = 0; l < n; ++l)
if (nums[l] > mn)
break;
int r;
for (r = n - 1; r >= 0; --r)
if (nums[r] < mx)
break;
return l < r ? r - l + 1 : 0;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.