LeetCode 581: Shortest Unsorted Continuous Subarray

Problem Description

LeetCode Problem 581

Given an integer array nums, you need to find one continuous subarray such that if you only sort this subarray in non-decreasing order, then the whole array will be sorted in non-decreasing 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 <= 104
• -105 <= nums[i] <= 105

Difficulty: Medium

Tags: array, two pointers, stack, greedy, sorting, monotonic stack

Rating: 96.69%

Solution Approach

Let’s solve this problem step by step:

1. First, we find the leftmost element that violates the sorted property by comparing adjacent elements from left to right.
2. Similarly, we find the rightmost violation by scanning from right to left.
3. Within the range we found, we determine the minimum and maximum values.
4. Finally, we extend our range if necessary by checking if elements outside our initial range need to be included in the sort.

Here’s the solution with detailed comments:

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 1: 
            return 0  # Arrays of length 0 or 1 are always sorted
        
        # Find the first element from left that is out of order
        l = 0
        for i in range(1, n):
            if nums[i] < nums[i-1]:
                l = i - 1
                break
        else:  # If we never found a violation, array is sorted
            return 0
        
        # Find the first element from right that is out of order
        r = n-1
        for i in range(n-2, -1, -1):
            if nums[i] > nums[i+1]:
                r = i + 1
                break
        
        # Find min and max in the unsorted portion
        min_val, max_val = min(nums[l:r+1]), max(nums[l:r+1])
        
        # Extend left boundary if we find larger elements
        for i in range(l):
            if nums[i] > min_val:
                l = i
                break
                
        # Extend right boundary if we find smaller elements
        for i in range(n-1, r, -1):
            if nums[i] < max_val:
                r = i
                break
                
        return r - l + 1

Detailed Walkthrough

Let’s walk through the example nums = [2,6,4,8,10,9,15]:

1. First Pass (finding initial boundaries):

   • We scan from left and find that 6 > 4 is our first violation
   • From right, we find that 10 > 9 is our last violation
   • Initial range: [6,4,8,10,9] (indices 1 to 5)

2. Finding min/max:

   • In our range [6,4,8,10,9]:
   • min_val = 4
   • max_val = 10

3. Extending boundaries:

   • Check left of range: 2 is less than min_val (4), so left boundary stays
   • Check right of range: 15 is greater than max_val (10), so right boundary stays
   • Final range remains [6,4,8,10,9]

4. Result:

   • Length of range = 5 (from index 1 to 5, inclusive)

Complexity Analysis

• Time Complexity: $O(n)$ where n is the length of the input array. We make a constant number of passes through the array.
• Space Complexity: $O(1)$ as we only use a constant amount of extra space regardless of input size.

Key Insights

1. The unsorted subarray might need to be larger than just the portion where elements are out of order.
2. The minimum and maximum values in the unsorted portion help us determine if we need to extend our boundaries.
3. The solution avoids sorting the entire array, which would be less efficient (O(n log n)).