###### Shortest Unsorted Continuous Subarray | February Leetcoding Challenge 2021 | Day 25
Manas Sinha
Developer | Designer

## Shortest Unsorted Continuous Subarray

`PROBLEM  STATEMENT:`
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.
Example 1
```strong>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
```
< Constraints:
• `1 <= nums.length <= 104`
• `-105 <= nums[i] <= 105`
Follow up: Can you solve it in `O(n)` time complexity?

## Explanation

`ALGORITHM: `
• Maintain a stack.
• Traverse the array from left to right.
• If current element is greater than previous element (rising slope), push the index in the array.
• Else pop the elements of stack until the element(corresponding to the index) on the top of the stack is less than the current element.If the popping stops with when stacks top is k, the current element’s correct position in k+1.
• We follow the same process while traversing over the whole array, and determine the value of minimum such k. This marks the left boundary of the unsorted subarray..
• Similarly, to find the right boundary of the unsorted subarray, we traverse over the numsnums array backwards.This time we keep on pushing the elements if we see a falling slope.
• Time complexity : O(n)
• Space complexity : O(n)

## C++

``````class Solution {
public:
int findUnsortedSubarray(vector<int>& nums) {
stack<int> st;
int l = nums.size();
int r = 0;

for(int i=0;i<nums.size();++i){
while(!st.empty() && nums[st.top()] > nums[i])
{
l = min(l,st.top());
st.pop();
}
st.push(i);
}
while(!st.empty()) st.pop();
for(int i=nums.size()-1;i>=0;--i){
while(!st.empty() && nums[st.top()] < nums[i])
{
r = max(r,st.top());
st.pop();
}
st.push(i);
}
return r-l > 0 ? r-l+1 : 0;
}
};``````

## PYTHON

``````class Solution:
def findUnsortedSubarray(self, nums: List[int]) -> int:
st = []
l = len(nums)
r = 0

for i in range(len(nums)):
while len(st) and nums[st[-1]]>nums[i]:
l = min(l,st[-1])
st.pop()
st.append(i)
st.clear()

for i in range(len(nums)-1,-1,-1):
while len(st) and nums[st[-1]] < nums[i]:
r = max(r,st[-1])
st.pop()
st.append(i)

return r-l+1 if r-l>0 else 0``````