LeetCode 581: Shortest Unsorted Continuous Subarray Solution in Python – A Step-by-Step Guide

What Is LeetCode 581: Shortest Unsorted Continuous Subarray?

In LeetCode 581: Shortest Unsorted Continuous Subarray, you’re given an integer array nums, and your task is to return the length of the shortest continuous subarray that, when sorted, results in the entire array being sorted in ascending order. If the array is already sorted, return 0. For example, with nums = [2,6,4,8,10,9,15], the shortest unsorted subarray is [6,4,8,10,9], length 5. This problem builds on LeetCode 88: Merge Sorted Array for array handling but focuses on identifying the minimal unsorted segment.

Problem Statement

• Input: nums (List[int])—array of integers.
• Output: Integer—length of shortest unsorted continuous subarray to sort.
• Rules: Subarray must be continuous; sorting it sorts entire array; return 0 if already sorted.

Constraints

• 1 <= nums.length <= 10⁴
• -10⁵ <= nums[i] <= 10⁵

Examples

• Input: nums = [2,6,4,8,10,9,15]
• Output: 5
• Subarray [6,4,8,10,9] (indices 1-5), length 5; sorting it fixes array.
• Input: nums = [1,2,3,4]
• Output: 0
• Already sorted.
• Input: nums = [1,3,2,2,2]
• Output: 4
• Subarray [3,2,2,2] (indices 1-4), length 4.

Understanding the Problem: Finding the Unsorted Chunk

To solve LeetCode 581: Shortest Unsorted Continuous Subarray in Python, we need to identify the shortest continuous segment in nums that, when sorted, makes the entire array sorted, returning its length, handling arrays up to 10⁴ elements efficiently. A brute-force approach checking all subarrays (O(n³)) is impractical. Instead, a two-pointer method comparing the array to its sorted version finds the unsorted boundaries in O(n) time, leveraging the fact that outside the unsorted segment, elements must align with the sorted order. We’ll explore:

• Best Solution (Two-Pointer Comparison with Sorted Array): O(n) time, O(1) space—fast and optimal (excluding sorting for explanation).
• Alternative Solution (Brute-Force Subarray Checking): O(n³) time, O(1) space—simple but slow.

Let’s dive into the two-pointer solution with a friendly breakdown!

Best Solution: Two-Pointer Comparison with Sorted Array

Why Two-Pointer Wins

The two-pointer comparison solution is the best for LeetCode 581 because it identifies the unsorted subarray in O(n) time and O(1) space (after an initial O(n log n) sort for clarity, though an O(n) alternative exists) by finding the leftmost and rightmost positions where the array deviates from its sorted version, efficiently pinpointing the boundaries without checking all subarrays. It’s like scanning a messy list with a sorted guide, marking where the chaos starts and ends—all in a swift, clever pass!

How It Works

Think of this as an array-boundary detective:

• Step 1: Check if Sorted:
• If nums matches sorted version, return 0.
• Step 2: Find Left Boundary:
• Scan from left until nums[i] > min(nums[i+1:]) (out of order).
• Step 3: Find Right Boundary:
• Scan from right until nums[i] < max(nums[:i]) (out of order).
• Step 4: Compute Length:
• Length = right - left + 1, or 0 if no boundaries found.
• Step 5: Return Result:
• Length of shortest unsorted subarray.
• Why It Works:
• Unsorted segment disrupts monotonicity; boundaries are where order breaks.
• Two passes efficiently locate start and end.

It’s like an unsorted-segment spotter!

Step-by-Step Example

Example: nums = [2,6,4,8,10,9,15]

• Step 1: Sorted = [2,4,6,8,9,10,15], not equal, proceed.
• Step 2: Left boundary:
• i=0: 2 ≤ min(6,4,8,10,9,15) = 4, ok.
• i=1: 6 > min(4,8,10,9,15) = 4, left = 1.
• Step 3: Right boundary:
• i=6: 15 ≥ max(2,6,4,8,10,9) = 10, ok.
• i=5: 9 < max(2,6,4,8,10) = 10, right = 5.
• Step 4: Length = 5 - 1 + 1 = 5.
• Result: 5.

Example: nums = [1,2,3,4]

• Step 1: Sorted = [1,2,3,4], equal, return 0.
• Result: 0.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners (using an O(n) approach without sorting for optimal runtime):

Copy codeclass Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        n = len(nums)

        # Step 1: Find left boundary (first number out of order)
        max_so_far = float('-inf')
        left = n  # Default to beyond array if fully sorted
        for i in range(n):
            max_so_far = max(max_so_far, nums[i])
            if i < n - 1 and nums[i] > nums[i + 1]:
                left = min(left, i)

        # Step 2: If no disorder found, array is sorted
        if left == n:
            return 0

        # Step 3: Find right boundary (last number out of order)
        min_so_far = float('inf')
        right = -1  # Default to before array if fully sorted
        for i in range(n - 1, -1, -1):
            min_so_far = min(min_so_far, nums[i])
            if i > 0 and nums[i] < nums[i - 1]:
                right = max(right, i)

        # Step 4: Compute and return length
        return right - left + 1

• Line 4: Get array length.
• Lines 7-11: Scan left to right:
• Track max seen so far.
• If current > next, mark as left boundary.
• Lines 14-15: If no left boundary, return 0 (sorted).
• Lines 18-22: Scan right to left:
• Track min seen so far.
• If current < previous, mark as right boundary.
• Line 25: Compute length from boundaries.
• Time Complexity: O(n)—two linear passes.
• Space Complexity: O(1)—minimal extra space.

It’s like an array-order sleuth!

Alternative Solution: Brute-Force Subarray Checking

Why an Alternative Approach?

The brute-force subarray checking approach tests all possible subarrays to find the shortest one that, when sorted, fixes the entire array, running in O(n³) time and O(1) space (excluding temp arrays). It’s thorough but impractical for large arrays, making it a good baseline for small inputs or understanding.

How It Works

Picture this as a subarray-sorting tester:

• Step 1: Generate all subarrays (start, end indices).
• Step 2: For each subarray, sort it and check if full array is sorted.
• Step 3: Track shortest length that works.
• Step 4: Return length (0 if sorted).

It’s like a subarray-fixing explorer!

Step-by-Step Example

Example: nums = [1,3,2]

• Step 1: Subarrays:
• [1], [1,3], [1,3,2], [3], [3,2], [2].
• Step 2: Test:
• [1,3,2]: Sort [3,2] → [1,2,3], sorted, length = 2.
• Others don’t fully sort array.
• Step 3: Shortest = 2.
• Result: 2.

Code for Brute-Force Approach

Copy codeclass Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        shortest = n + 1  # Default to beyond array

        # Step 1: Check if already sorted
        if all(nums[i] <= nums[i + 1] for i in range(n - 1)):
            return 0

        # Step 2: Test all subarrays
        for start in range(n):
            for end in range(start, n):
                temp = nums[:start] + sorted(nums[start:end + 1]) + nums[end + 1:]
                if all(temp[i] <= temp[i + 1] for i in range(n - 1)):
                    shortest = min(shortest, end - start + 1)
                    break  # Found a valid subarray, move to next start

        # Step 3: Return result
        return shortest if shortest <= n else 0

• Line 6-7: Check if sorted, return 0.
• Lines 10-16: Nested loops test subarrays, sort, check if fixes array.
• Line 19: Return shortest length or 0.
• Time Complexity: O(n³)—subarray generation and sorting.
• Space Complexity: O(1)—temp array excluded.

It’s a brute-force subarray fixer!

Comparing the Two Solutions

• Two-Pointer (Best):
• Pros: O(n), O(1), fast.
• Cons: Boundary logic.
• Brute-Force (Alternative):
• Pros: O(n³), O(1), thorough.
• Cons: Very slow.

Two-pointer wins for efficiency!

Additional Examples and Edge Cases

• [1]: 0.
• [2,1]: 2.
• All equal: 0.

Two-pointer handles them all!

Complexity Recap

• Two-Pointer: Time O(n), Space O(1).
• Brute-Force: Time O(n³), Space O(1).

Two-pointer’s the speed champ!

Key Takeaways

• Two-Pointer: Boundary finesse—learn at Python Basics!
• Brute-Force: Subarray probe.
• Arrays: Sorting is fun.
• Python: Pointers or brute, your pick!

Final Thoughts: Find That Subarray!

LeetCode 581: Shortest Unsorted Continuous Subarray in Python is a clever array challenge. Two-pointer comparison is your fast track, while brute-force offers a thorough dive. Want more? Try LeetCode 88: Merge Sorted Array or LeetCode 75: Sort Colors. Ready to sort? Head to Solve LeetCode 581 on LeetCode and measure that subarray today!