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

# 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