# Shortest Unsorted Continuous Subarray

## Description

Given an integer array, 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, too.

You need to find the **shortest** such subarray and output its length.

**Example 1:**

```
Input: [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.
```

**Note:**

1. Then length of the input array is in range \[1, 10,000].
2. The input array may contain duplicates, so ascending order here means **<=**.

## Solution

Idea:

1. Find longest subarray `nums[0..right]` such that `max(nums[0..right]) <= nums[right+1..n-1]`.
2. Find longest subarray `nums[left..n-1]` such that `min(nums[left..n-1]) >= nums[0..left-1]`.
3. The shortest subarray we want to find is `nums[left..right]`. We can prove it by contradiction.

```cpp
class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int n = nums.size();
        if(n < 2) return 0;
        int left = 1, right = 0;
        int max_num = INT_MIN, min_num = INT_MAX;
        for(int i = 0, j = n - 1; i < n; ++i, --j){
            if(max_num > nums[i])
                right = i;
            else
                max_num = nums[i];
            if(min_num < nums[j])
                left = j;
            else
                min_num = nums[j];
        }
        return right - left + 1;
    }
};
```
