# 581 Shortest Unsorted Continuous Subarray

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 **<=.**

**The Idea:** Find the first element iterating from the left that creates a conflict in creating an ascending array. Do the same thing iterating from the right. At this point, everything to the right of `left` is sorted, and everything to the right of `right` is sorted. The only thing left to do is to adapt our subarray between `[left:right]` so that it create an entire sorted array. The way this is done is my moving the minimum element in `[left:right]` to its rightful place on towards the left, and moving the maximum element in `[left:right]` to its rightful place towards the right. As these elements get moved our left and right will expand.

**Complexity:** O(N) time and O(1) space

```python
# this one is a gem: beat 100% submissions at the time

class Solution:
    def findUnsortedSubarray(self, ar):
        """
        :type nums: List[int]
        :rtype: int
        """
        left, right = 0, len(ar) - 1

        # find the first conflict from the left side
        while (left < len(ar) - 1):
            if ar[left] > ar[left + 1]:
                break
            left += 1

        # entire array is sorted
        if left == len(ar) - 1 or not ar:
            return 0

        # find the first conflict from the right
        while (right >= 1):
            if ar[right - 1] > ar[right]:
                break
            right -= 1

        # entire array is unsorted
        if left == len(ar) - 1:
            return len(ar)

        # now adjust left and right so that the array becomes sorted
        min_l, max_r = min(ar[left:right + 1]), max(ar[left:right + 1]),

        # while the element to the left is greater than min_l
        while (left >= 1 and min_l < ar[left - 1]):
            left -= 1

        # while the element to the right is smaller than max_r
        while (right < len(ar) - 1 and max_r > ar[right + 1]):
            right += 1

        return right - left + 1
```