LeetCode 581. Shortest Unsorted Continuous Subarray

Problem: Given an integer array nums, find the smallest subarray that needs to be sorted (ascending) in order for the whole array to be sorted. Return the length of the subarray.

Example:
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.

Solution 1

Before jumping into coding, let’s think about this question: when is an array sorted? An array is sorted (in an ascending order) when each element is in place, meaning greater than or equal to the previous element AND smaller than or equal to the next element in the array. If an element doesn’t fulfil these two requirements, it is out of place.

Now the question is, which other elements should we include in the subarray if an element E is out of place? Well, if we check from the beginning of the array, if an element appears before E and is greater than E, then it is out of place too. Likewise, if an element appears after E and is smaller than E, it also needs to be re-sorted, too.

Following this logic, we have our first solution. For each element E in nums, we need to loop through the array nums to update the minimum and maximum index of the subarray. This algorithm has a time complexity of O(n**2) and a space complexity of O(1).

Solution 2

In solution 1, we need to loop through the array for each out-of-place element. Is there a more efficient way to solve this problem?

It turns out that we can simplify the process by first looping through the array once and identifying the minimum and maximum out-of-place elements (minNum and maxNum). All the numbers within the range of minNum and maxNum need to be re-sorted. Therefore, in the second pass, we will loop through the array again and find all the elements within this range, and update the lower and upper bounds of the subarray accordingly.

With this approach, the time complexity is reduced to O(n), while the space complexity stays the same.

class Solution:
    def outOfPlace(self, nums, i):
        if i == 0:
            return True if nums[i] > nums[i + 1] else False
        elif i == len(nums) - 1:
            return True if nums[i] < nums[i - 1] else False
        elif nums[i] < nums[i - 1] or nums[i] > nums[i + 1]:
            return True
        return False
        
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        if len(nums) == 1: return 0
        minNum, maxNum = float("inf"), -float("inf")
        
        for i in range(len(nums)):
            if self.outOfPlace(nums, i):
                minNum = min(minNum, nums[i])
                maxNum = max(maxNum, nums[i])
        
        if minNum == float("inf"):
            return 0
        
        subarray = [float("inf"), -float("inf")]
        for i in range(len(nums)):
            if nums[i] > minNum:
                subarray[0] = min(subarray[0], i)
            if nums[i] < maxNum:
                subarray[1] = max(subarray[1], i)
                
        return subarray[1] - subarray[0] + 1

Time: O(n), space: O(1)

Hopefully, you have found this article useful.

If you like my stories, don’t forget to give them a clap 👏 .

Please follow me and share the article with your friends! Cheers! 😉