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:

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

Difficulty: introductory

Starter code:

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        

Solutions:
class Solution:
     def findUnsortedSubarray(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         left = 1
         size = len(nums)
         if size == 0:
             return 0
         while left < size and nums[left - 1] <= nums[left]:
             left += 1
         if left == size:
             return 0
         left -= 1
         right = size - 1
         while right > 0 and nums[right] >= nums[right - 1]:
             right -= 1
         sub = nums[left : right + 1]
         min_ = min(sub)
         max_ = max(sub)
         for i in range(left):
             if nums[i] > min_:
                 left = i
                 break
         for i in range(size - 1, right, -1):
             if nums[i] < max_:
                 right = i
                 break
         return right - left + 1


class Solution(object):
     def findUnsortedSubarray(self, nums):
         nums = [float('-inf')] + nums + [float('inf')]
         '''find left boundary'''
         left = 0
         while left<len(nums)-1 and nums[left]<=nums[left+1]:
             left += 1
         # return 0 if already sorted ascending
         if left == len(nums)-1:
             return 0
         min_num = min(nums[left+1:])
         while nums[left] > min_num:
             left -= 1
         '''find right boundary'''
         right = len(nums)-1
         while right>0 and nums[right-1]<=nums[right]:
             right -= 1
         # return 0 if sorted descending
         if right == 0:
             return 0
         max_num = max(nums[:right])
         while nums[right] < max_num:
             right += 1
         return right - left - 1

class Solution:
     def findUnsortedSubarray(self, nums):
         if len(nums) == 1:
             return 0
         
         start = -1
         end = -1
         for i in range(len(nums)-1):
             if nums[i] > nums[i+1]:
                 start = i
                 break
         for i in reversed(list(range(1,len(nums)))):
             if nums[i] < nums[i-1]:
                 end = i
                 break
         if start == -1:
             return 0
         
         minimum = 10000000000000
         maximum = -10000000000000
         
         for i in range(start, end+1):
             if nums[i] > maximum:
                 maximum = nums[i]
             if nums[i] < minimum:
                 minimum = nums[i]
         
         for i in range(0, len(nums)):
             if nums[i] > minimum:
                 start = i
                 break
         for i in reversed(list(range(len(nums)))):
             if nums[i] < maximum:
                 end = i
                 break
         return end - start + 1
             


class Solution:
     def findUnsortedSubarray(self, nums):
         """ Improved algorithm.
         Time complexity: O(n). Space complexity: O(1).
         """
         n = len(nums)
         # special case
         if n < 2:
             return 0
 
         # find index of the min number of the unsorted subarray from the left
         left = n - 1
         for i in range(n - 1):
             if nums[i] > nums[i + 1]:
                 left = i + 1
                 break
         min_i = left
         for i in range(left + 1, n):
             if nums[i] < nums[min_i]:
                 min_i = i
 
         # find index of max number of the unsorted subarray from the right
         right = 0
         for i in range(n - 1, 0, -1):
             if nums[i] < nums[i - 1]:
                 right = i - 1
                 break
         max_i = right
         for i in range(max_i - 1, -1, -1):
             if nums[i] > nums[max_i]:
                 max_i = i
 
         # find the correct position of number at min index
         for i in range(min_i):
             if nums[i] > nums[min_i]:
                 min_i = i
                 break
 
         # find the correct position of number at max index
         for i in range(n - 1, max_i, -1):
             if nums[i] < nums[max_i]:
                 max_i = i
                 break
 
         # return length of unsorted subarray
         length = max_i - min_i + 1
         return length if length > 0 else 0


class Solution(object):
     def findUnsortedSubarray(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         n, lst = len(nums), sorted(nums)
         for i in range(n):
             if lst[i] != nums[i]:
                 L = i
                 break
         else:
             return 0
         for i in range(n - 1, -1, -1):
             if lst[i] != nums[i]:
                 R = i
                 break
         return R - L + 1


class Solution:
     def findUnsortedSubarray(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         n = len(nums)
         nums_sorted = sorted(nums)
         is_same = [a == b for a, b in zip(nums, nums_sorted)]
         return 0 if all(is_same) else n - is_same.index(False) - is_same[::-1].index(False)
             


class Solution:
     def findUnsortedSubarray(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         lens = len(nums)
         t = nums
         t = sorted(t)
         print(nums)
         t1 = lens
         t2 = 0
         for i in range(lens-1):
             if nums[i] != t[i]:
                 t1 = i
                 break
         for i in range(lens-1,0,-1):
             if nums[i] != t[i]:
                 t2 = i
                 break;
         print(t2)
         return max(t2-t1+1,0)


class Solution:
     def findUnsortedSubarray(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         a = sorted(nums)
         start = -1
         end = -1
         for i in range(len(a)):
             if a[i] != nums[i] and start == -1:
                 start = i
             elif a[i] != nums[i]:
                 end = i
         
         if start == -1:
             return 0
         
         return end - start + 1
             


class Solution:
     def findUnsortedSubarray(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         sort_nums = sorted(nums)
         diff = list(map(lambda x, y: x - y, sort_nums, nums))
         start, end = 0, len(nums) - 1
         while start < end:
             if diff[start] == 0:
                 start += 1
                 
             if diff[end] == 0:
                 end -= 1
             
             if diff[start] and diff[end]:
                 break
         
         if end > start:
             return end - start + 1
         else:
             return 0