Problem Description

You are given an integer array nums. Your task is to find the shortest continuous subarray within this array such that if you sort only this subarray in non-decreasing order (ascending order), the entire array becomes sorted in non-decreasing order.

For example, if you have an array like [2, 6, 4, 8, 10, 9, 15], you need to identify that sorting the subarray [6, 4, 8, 10, 9] (from index 1 to 5) would make the entire array sorted as [2, 4, 6, 8, 9, 10, 15].

The problem asks you to return the length of this shortest subarray that needs to be sorted. If the array is already sorted, the length would be 0.

The solution approach works by:

1. Creating a sorted version of the original array
2. Finding the leftmost position where the original array differs from the sorted array (this is where the unsorted portion begins)
3. Finding the rightmost position where the original array differs from the sorted array (this is where the unsorted portion ends)
4. The distance between these two positions plus 1 gives the length of the subarray that needs to be sorted

The code uses two pointers l and r starting from the beginning and end of the array respectively. It moves l forward as long as elements match between the original and sorted arrays, and moves r backward as long as elements match. The formula r - l + 1 gives the length of the subarray between these positions.

Intuition

The key insight is that if we need to sort only a portion of the array to make the entire array sorted, then the elements outside this portion must already be in their correct final positions.

Think about what happens when we sort an array - each element moves to its correct position. If an element is already in its correct position, it doesn't need to move. So we can identify which elements need to be rearranged by comparing the original array with what it should look like when fully sorted.

When we create a sorted version of the array and compare it with the original:

• Elements at the beginning that are already in their correct positions don't need to be included in the subarray we sort
• Elements at the end that are already in their correct positions also don't need to be included

The elements that differ between the original and sorted arrays are exactly those that need to be rearranged. The leftmost difference marks where the unsorted portion begins, and the rightmost difference marks where it ends.

For example, with nums = [2, 6, 4, 8, 10, 9, 15]:

• Sorted version: [2, 4, 6, 8, 9, 10, 15]
• Comparing position by position:
  • Position 0: 2 == 2 ✓ (already correct)
  • Position 1: 6 != 4 ✗ (needs sorting)
  • Position 2: 4 != 6 ✗ (needs sorting)
  • ...continuing...
  • Position 5: 9 != 10 ✗ (needs sorting)
  • Position 6: 15 == 15 ✓ (already correct)

The differences occur from index 1 to 5, so we need to sort that subarray of length 5 - 1 + 1 = 5.

This approach naturally handles edge cases - if the array is already sorted, no positions will differ, and the pointers will cross, resulting in a length of 0.

Learn more about Stack, Greedy, Two Pointers, Sorting and Monotonic Stack patterns.

Solution Approach

The implementation uses a sorting-based approach to find the shortest unsorted subarray:

1. Create a sorted copy: First, we create a sorted version of the input array using sorted(nums). This gives us the target state that we want to achieve.

2. Initialize two pointers: We set up two pointers:

   • l (left pointer) starting at index 0
   • r (right pointer) starting at the last index len(nums) - 1

3. Find the left boundary: We move the left pointer l forward as long as:

   • l <= r (pointers haven't crossed)
   • nums[l] == arr[l] (element at position l is already in its correct sorted position)

   When this loop stops, l points to the first position where the element differs from its sorted position, marking the start of the unsorted subarray.

4. Find the right boundary: Similarly, we move the right pointer r backward as long as:

   • l <= r (pointers haven't crossed)
   • nums[r] == arr[r] (element at position r is already in its correct sorted position)

   When this loop stops, r points to the last position where the element differs from its sorted position, marking the end of the unsorted subarray.

5. Calculate the length: The length of the shortest unsorted subarray is r - l + 1.

The condition l <= r in both loops handles the edge case where the array is already sorted. In this case, l will increment all the way past r, and the formula r - l + 1 will give a non-positive number, which effectively returns 0 (since at that point l > r).

Time Complexity: O(n log n) due to the sorting operation Space Complexity: O(n) for storing the sorted copy of the array

Example Walkthrough

Let's walk through the solution with the array nums = [1, 3, 2, 4, 5].

Step 1: Create sorted version

• Original: [1, 3, 2, 4, 5]
• Sorted: [1, 2, 3, 4, 5]

Step 2: Initialize pointers

• l = 0 (pointing to first element)
• r = 4 (pointing to last element)

Step 3: Find left boundary

• Check position 0: nums[0] = 1, sorted[0] = 1 → They match! Move l forward
• l = 1
• Check position 1: nums[1] = 3, sorted[1] = 2 → They differ! Stop here
• Left boundary found at index l = 1

Step 4: Find right boundary

• Check position 4: nums[4] = 5, sorted[4] = 5 → They match! Move r backward
• r = 3
• Check position 3: nums[3] = 4, sorted[3] = 4 → They match! Move r backward
• r = 2
• Check position 2: nums[2] = 2, sorted[2] = 3 → They differ! Stop here
• Right boundary found at index r = 2

Step 5: Calculate length

• The unsorted subarray spans from index 1 to index 2
• Length = r - l + 1 = 2 - 1 + 1 = 2

Verification: If we sort the subarray [3, 2] at indices 1-2, it becomes [2, 3], making the entire array [1, 2, 3, 4, 5] which is sorted! ✓

The algorithm correctly identifies that we need to sort a subarray of length 2.

Solution Implementation

Time and Space Complexity

The time complexity is O(n × log n), where n is the length of the array. This is dominated by the sorting operation sorted(nums), which uses Python's Timsort algorithm with O(n × log n) time complexity. The two while loops that follow each iterate through the array at most once, contributing O(n) time, but this is absorbed by the larger sorting complexity.

The space complexity is O(n), where n is the length of the array. This is because the sorted() function creates a new sorted copy of the input array nums, which requires O(n) additional space to store all elements.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Duplicate Elements Mishandling

One common pitfall occurs when dealing with duplicate elements at the boundaries of the unsorted region. Consider the array [1, 2, 3, 3, 3]. The current approach works correctly, but developers often mistakenly try to optimize by skipping duplicates, which can lead to incorrect boundary detection.

Example of problematic scenario:

nums = [1, 3, 2, 3, 3]
# Sorted: [1, 2, 3, 3, 3]

If someone tries to "optimize" by skipping equal adjacent elements before comparing with the sorted array, they might miss that the 3 at index 1 needs to be part of the subarray to be sorted.

2. Edge Case: Already Sorted Array

While the current solution handles this correctly through the left <= right condition, a common mistake is forgetting to check if the pointers have crossed. Without this check, the code might continue comparing beyond valid boundaries or return incorrect negative values.

Incorrect implementation example:

# WRONG: Missing pointer crossing check
while nums[left] == sorted_nums[left]:  # Can cause index out of bounds
    left += 1

3. Memory Optimization Attempt Leading to Incorrect Results

Developers might try to avoid creating a sorted copy to save space, attempting to find boundaries by just comparing adjacent elements or looking for inversions. This approach often fails for cases like:

nums = [1, 3, 2, 2, 2]
# Simply looking for inversions might incorrectly identify only [3, 2] as needing sorting
# But actually [3, 2, 2, 2] needs to be sorted to get [1, 2, 2, 2, 3]

4. Alternative O(n) Solution Complexity

While an O(n) solution exists using min/max tracking, it's more error-prone:

def findUnsortedSubarray(self, nums: List[int]) -> int:
    n = len(nums)
    if n <= 1:
        return 0
  
    # Find initial boundaries
    left = n
    right = 0
  
    # Track max from left and min from right
    max_so_far = float('-inf')
    min_so_far = float('inf')
  
    # Find right boundary
    for i in range(n):
        max_so_far = max(max_so_far, nums[i])
        if nums[i] < max_so_far:
            right = i
  
    # Find left boundary
    for i in range(n-1, -1, -1):
        min_so_far = min(min_so_far, nums[i])
        if nums[i] > min_so_far:
            left = i
  
    return 0 if right <= left else right - left + 1

This O(n) approach is harder to understand and more prone to implementation errors, making the sorting-based solution often preferable despite its higher time complexity.