LeetCode Solutions
581. Shortest Unsorted Continuous Subarray
Time: $O(n)$ Space: $O(1)$
class Solution {
public:
int findUnsortedSubarray(vector<int>& nums) {
const int n = nums.size();
int mini = INT_MAX;
int maxi = 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)
mini = min(mini, nums[i]);
}
for (int i = n - 2; i >= 0; --i) {
if (nums[i] > nums[i + 1])
meetIncrease = true;
if (meetIncrease)
maxi = max(maxi, nums[i]);
}
int l;
for (l = 0; l < n; ++l)
if (nums[l] > mini)
break;
int r;
for (r = n - 1; r >= 0; --r)
if (nums[r] < maxi)
break;
return l < r ? r - l + 1 : 0;
}
};
class Solution {
public int findUnsortedSubarray(int[] nums) {
final int n = nums.length;
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
boolean meetDecrease = false;
boolean meetIncrease = false;
for (int i = 1; i < n; ++i) {
if (nums[i] < nums[i - 1])
meetDecrease = true;
if (meetDecrease)
min = Math.min(min, nums[i]);
}
for (int i = n - 2; i >= 0; --i) {
if (nums[i] > nums[i + 1])
meetIncrease = true;
if (meetIncrease)
max = Math.max(max, nums[i]);
}
int l = 0;
for (l = 0; l < n; ++l)
if (nums[l] > min)
break;
int r = 0;
for (r = n - 1; r >= 0; --r)
if (nums[r] < max)
break;
return l > r ? 0 : r - l + 1;
}
}
class Solution:
def findUnsortedSubarray(self, nums: List[int]) -> int:
mini = math.inf
maxi = -math.inf
flag = False
for i in range(1, len(nums)):
if nums[i] < nums[i - 1]:
flag = True
if flag:
mini = min(mini, nums[i])
flag = False
for i in reversed(range(len(nums) - 1)):
if nums[i] > nums[i + 1]:
flag = True
if flag:
maxi = max(maxi, nums[i])
for l in range(len(nums)):
if nums[l] > mini:
break
for r, num in reversed(list(enumerate(nums))):
if num < maxi:
break
return 0 if l >= r else r - l + 1