# 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. 1.
Then length of the input array is in range [1, 10,000].
2. 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
# 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