Java, C++, O(n) Time O(1) Space

• 1, Define two indices left and right, left is first N[i] > N[i+1] (start from 0) and right is first N[i-1] > N[i] (from length-1).
2, Find min and max from left to right.
3, Expand left so that N[left] < min and expand right so that N[right] > max.

Java

``````    public int findUnsortedSubarray(int[] nums) {
int left = nums.length-1, right = 0;
for(int i = 0; i < nums.length-1; i++){
if(nums[i] > nums[i+1]){
left = i;
break;
}
}
for(int i = nums.length-1; i > 0; i--){
if(nums[i] < nums[i-1]){
right = i;
break;
}
}

// No change.
if(left >= right)
return 0;

int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
for(int i = left; i <= right; i++){
min = Math.min(nums[i], min);
max = Math.max(nums[i], max);
}
// expand left and right
while(left >= 0 && nums[left] > min)
left--;
while(right < nums.length && nums[right] < max)
right++;

return right-left-1;
}
``````

C++

``````    int findUnsortedSubarray(vector<int>& nums) {
int left = nums.size()-1, right = 0;
for(int i = 0; i < nums.size()-1; ++i)
{
if(nums[i] > nums[i+1])
{
left = i;
break;
}
}
for(int i = nums.size()-1; i > 0; --i)
{
if(nums[i] < nums[i-1])
{
right = i;
break;
}
}
if(left >= right)
return 0;
int minVal = INT_MAX, maxVal = INT_MIN;
for(int i = left; i <= right; ++i)
{
minVal = min(minVal, nums[i]);
maxVal = max(maxVal, nums[i]);
}
while(left >= 0 && nums[left] > minVal)
left--;
while(right < nums.size() && nums[right] < maxVal)
right++;
return right-left-1;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.