# 16.Shortest Unsorted Continuous Subarray

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:
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

Example 4:
Input: nums = [1,2,2,2,3]
Output: 4
```

## Solution I : (Using sorting)

```cpp
class Solution
{
public:
    int findUnsortedSubarray(vector<int> &nums)
    {

        vector<int> v = nums;

        sort(v.begin(), v.end());

        int start = -1, end = -1;
        for (int i = 0; i < nums.size(); i++)
        {
            if (nums[i] != v[i])
            {
                start = i;
                break;
            }
        }

        for (int i = nums.size() - 1; i >= 0; i--)
        {
            if (nums[i] != v[i])
            {
                end = i;
                break;
            }
        }
        
        if(start == end){
            return 0;
        }
        return (end - start) + 1;
    }
};
```

**Time Complexity : O(N log N), Space Complexity: O(N)**

## Solution II: (Using Stack)

**Approach:**\
**Finding the correct position of the minimum element in the unsorted subarray helps to determine the required left boundary.** \
**Similarly, the correct position of the maximum element in the unsorted subarray helps to determine the required right boundary.**

![Unsorted\_subarray](https://leetcode.com/problems/shortest-unsorted-continuous-subarray/Figures/581/Unsorted_subarray_2.PNG)

```cpp
class Solution
{
public:
    int findUnsortedSubarray(vector<int> &nums)
    {

        int n = nums.size();
        stack<int> s;
        s.push(0);
        int minStart = n;
        int maxEnd = -1;

        for (int i = 1; i < nums.size(); i++)
        {
            if (nums[i] < nums[s.top()])
            {

                while (!s.empty() && nums[s.top()] > nums[i])
                {
                    s.pop();
                }

                if (!s.empty() && s.top() < minStart)
                {
                    minStart = s.top() + 1;
                }
                else if (s.empty())
                {
                    minStart = 0;
                }
            }

            s.push(i);
        }

        stack<int> rs;
        rs.push(n - 1);

        for (int i = n - 2; i >= 0; i--)
        {
            if (nums[i] > nums[rs.top()])
            {
                while (!rs.empty() && nums[rs.top()] < nums[i])
                {
                    rs.pop();
                }

                if (!rs.empty() && rs.top() > maxEnd)
                {
                    maxEnd = rs.top() - 1;
                }
                else if (rs.empty())
                {
                    maxEnd = n - 1;
                }
            }

            rs.push(i);
        }

        return ((maxEnd - minStart) > 0) ? (maxEnd - minStart + 1) : 0;
    }
};
```

**Time Complexity : O(N), Space Complexity: O(N)**