581. Shortest Unsorted Continuous Subarray
1. Description
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.
2. Example
Example 1:
Input: nums = [2,6,4,8,10,9,15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.
Example 2:
Input: nums = [1,2,3,4]
Output: 0
Example 3:
Input: nums = [1]
Output: 0
3. Constraints
- 1 <= nums.length <= $10^4$
- $-10^5$ <= nums[i] <= $10^5$
4. Follow Up
- Can you solve it in O(n) time complexity?
5. Solutions
My Accepted Solution
n = i_nums.size()
Time complexity: O($nlog_2n$)
Space complexity: O(n)
// we sort the array, then, we compare every origin element and sorted element, when they are different, we find the element needs to be sorted
class Solution {
public:
// int findUnsortedSubarray(vector<int>& nums)
int findUnsortedSubarray(const vector<int>& i_nums) {
vector<int> sortedNums = i_nums;
sort(sortedNums.begin(), sortedNums.end());
int left = INT_MAX, right = INT_MIN;
for (int i = 0; i < i_nums.size(); ++i) {
if (i_nums[i] != sortedNums[i]) {
left = min(i, left);
right = max(i, right);
}
}
return right - left >= 0 ? right - left + 1 : 0;
}
};
5.1 Stack(Follow Up)
n = i_nums.size()
Time complexity: O(n)
Space complexity: O(n)
class Solution {
public:
// int findUnsortedSubarray(vector<int>& nums)
int findUnsortedSubarray(const vector<int>& i_nums) {
stack<int> increaseNums; // store indexes rather than values
int left = INT_MAX;
for (int i = 0; i < i_nums.size(); ++i) {
while (!increaseNums.empty() && i_nums[increaseNums.top()] > i_nums[i]) {
// now increaseNums.top() is the index that min value in the unsorted should be
left = min(increaseNums.top(), left);
increaseNums.pop();
}
increaseNums.push(i);
}
stack<int> decreaseNums;
int right = INT_MIN;
for (int i = i_nums.size() - 1; i >= 0; --i) {
while (!decreaseNums.empty() && i_nums[decreaseNums.top()] < i_nums[i]) {
right = max(decreaseNums.top(), right);
decreaseNums.pop();
}
decreaseNums.push(i);
}
return right >= left ? right - left + 1 : 0;
}
};
5.2 Find Min and Max Values(Follow Up)
n = i_nums.size()
Time complexity: O(n)
Space complexity: O(1)
class Solution {
public:
// int findUnsortedSubarray(vector<int>& nums)
int findUnsortedSubarray(const vector<int>& i_nums) {
int minValue = INT_MAX; // find the min value in the array
for (int i = 1; i < i_nums.size(); ++i) {
if (minValue == INT_MAX && i_nums[i] < i_nums[i - 1]) {
minValue = i_nums[i];
}
if (minValue != INT_MAX) {
minValue = min(i_nums[i], minValue);
}
}
int maxValue = INT_MIN; // find the max value in the array
for (int i = i_nums.size() - 2; i >= 0; --i) {
if (maxValue == INT_MIN && i_nums[i] > i_nums[i + 1]) {
maxValue = i_nums[i];
}
if (maxValue != INT_MIN) {
maxValue = max(i_nums[i], maxValue);
}
}
int left = INT_MAX; // find the left border
for (int i = 0; i < i_nums.size(); ++i) {
if (i_nums[i] > minValue) {
left = i;
break;
}
}
int right = INT_MIN; // find the right border
for (int i = i_nums.size() - 1; i >= 0; --i) {
if (i_nums[i] < maxValue) {
right = i;
break;
}
}
return right >= left ? right - left + 1 : 0;
}
};