Shortest Unsorted Continuous Subarray

Patrick Leaton
Published: March 24, 2021, 8:49 p.m.
Problem Description

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

Return the shortest such subarray and output its length.

 

Example 1:

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

Example 2:

Input: nums = [1,2,3,4]
Output: 0

Example 3:

Input: nums = [1]
Output: 0

 

Constraints:

  • 1 <= nums.length <= 10^4
  • -10^5 <= nums[i] <= 10^5

 

The description was taken from https://leetcode.com/problems/shortest-unsorted-continuous-subarray/.

Problem Solution

#O(N) Time, O(1) Space
class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        if len(nums) < 2:
            return 0
       
        min_sort, max_sort = float('inf'), float('-inf')
        left, right = 0, len(nums) -1
       
        for i, num in enumerate(nums):
            if self.not_ordered(i, num, nums):
                min_sort = min(min_sort, num)
                max_sort = max(max_sort, num)
 
        if max_sort == float('-inf'):
            return 0
 
        while min_sort >= nums[left]:
            left += 1
        while max_sort <= nums[right]:
            right -=1
        return 1 + right - left
 
    def not_ordered(self, i:int, num:int, nums: List) -> bool:
        if i == 0:
            return num > nums[i+1]
        elif i == len(nums)-1:
            return num < nums[i-1]
        else:
            return num > nums[i+1] or num < nums[i-1]

Problem Explanation

The approach that may come to mind right away is to make a copy of the array, sort it, then have two pointers moving inward to find the first two mismatched indices.  That would be O(N(Log N)) Time and O(N) Space.

What we could do instead is find the smallest and greatest values that are out of order, then move two pointers to the final positions these two values are supposed to be in within a sorted order, and then calculate the distance between these final locations.

Let's say that we have for example, [2,3,4,5,6,7,1] as an input.  We can see that only one needs to be put into position.

However, that means that we need to move the one all the way to the left of the sorted array partition to index zero, making the entire array unsorted.  Not only that, but we also need to move the seven to its correct position at index six.

That makes the final length of the unsorted array the last index minus the first index, the entire array.

If the length of the input array is less than two, then that means there can't be any unsorted elements so we will return zero.

        if len(nums) < 2:
            return 0

 

Next, we will initialize our minimum and maximum unsorted elements to infinity and negative infinity.  We will also initialize our left and right pointers to be the first and the last indices of the array.

        min_sort, max_sort = float('inf'), float('-inf')
        left, right = 0, len(nums) -1

Let's go ahead and create our helper function that tests for unordered values.  

It will take in an index, the number value, and the array.

    def not_ordered(self, i:int, num:int, nums: List) -> bool:

 

If we are at the first index, we will check if the element's value is greater than the element to its right.

Remember, the array is supposed to be sorted in ascending order.  

        if i == 0:
            return num > nums[i+1]

 

If we are at the last index, we will check if the element's value is less than the element to its left.

        elif i == len(nums)-1:
            return num < nums[i-1]

 

Otherwise, we will check if the element's value is either greater than the element to its right or less than the element to its left. 

        else:
            return num > nums[i+1] or num < nums[i-1]

 

Now that we have our helper function made, we can begin enumerating through the array.

An enumeration is a traversal through the values while also keeping a counter for us. 

Within each iteration, we'll be checking if our current index and value are not ordered by passing the index, value, and array to our helper function.

        for i, num in enumerate(nums):
            if self.not_ordered(i, num, nums):

 

We will keep track of the minimum value that is out of order and the maximum value that is also out of order.

                min_sort = min(min_sort, num)
                max_sort = max(max_sort, num)

 

Once we have our minimum and maximum out-of-order values, we will first check if the maximum value is negative infinity.  If it is, then that means the array is sorted already.

        if max_sort == float('-inf'):
            return 0

 

Otherwise, we'll move our pointers to the final locations of where the unsorted values should be.  

This is for test cases like this: [2,6,4,8,10,9,15]

We can see that the minimum unsorted number is four and the maximum is ten.  We use the pointers to let us know that the left boundary of the unsorted subarray is at index one and the right boundary is at the sixth index.  These are where the unsorted numbers need to end up for the subarray to be sorted.

Next, we'll move the left pointer to the right until the value at the left index is greater than the minimum unsorted value. 

        while min_sort >= nums[left]:
            left += 1

 

We will also move the right pointer to the left until the value at the right index is less than the maximum unsorted value.

        while max_sort <= nums[right]:
            right -=1

 

Once we have the left and right pointers at these final correct locations, we can subtract the right index by the left index to get their distance and add one to that value to get how many values are within that range.

We can then return this value.

        return 1 + right - left