Solution Explanation for Shortest Unsorted Continuous Subarray

The problem asks to find the shortest continuous subarray within a given array nums that, when sorted, would make the entire array sorted in non-decreasing order. The solution can be approached in two ways: sorting the entire array and comparing it to the original, or using a two-pointer approach that maintains maximum and minimum values during traversal.

Approach 1: Sorting and Comparison (O(n log n) time complexity)

This approach leverages the simplicity of sorting.

1. Sort a copy: Create a sorted copy of the input array nums. This step uses a standard sorting algorithm, resulting in O(n log n) time complexity.

2. Find differing indices: Iterate through both the original and sorted arrays simultaneously. Identify the leftmost index (l) where the original and sorted arrays differ, and the rightmost index (r) where they differ.

3. Calculate subarray length: The length of the shortest unsorted continuous subarray is r - l + 1. If l and r remain unchanged (no differences found), the array is already sorted, and the result is 0.

Approach 2: Two-Pointer Traversal (O(n) time complexity)

This approach is more efficient, achieving linear time complexity.

1. Initialize: Set l and r to -1. These will track the left and right boundaries of the unsorted subarray. Initialize mi (minimum) to infinity and mx (maximum) to negative infinity.

2. Left-to-right traversal: Iterate through the array from left to right.

   • If the current element x is less than the current maximum mx, it's out of order, so update r to the current index.
   • Otherwise, update mx to the current element.

3. Right-to-left traversal: Iterate through the array from right to left.

   • If the current element is greater than the current minimum mi, it's out of order, so update l to the current index.
   • Otherwise, update mi to the current element.

4. Return length: If r remains -1, the array was already sorted. Otherwise, the length of the unsorted subarray is r - l + 1.

Time Complexity Analysis:

• Approach 1: O(n log n) due to the sorting step.
• Approach 2: O(n) because it involves two single passes through the array.

Space Complexity Analysis:

• Approach 1: O(n) because a copy of the array is created for sorting.
• Approach 2: O(1) because it uses only a constant amount of extra space.

Code Examples (Python)

Approach 1:

def findUnsortedSubarray(nums):
    sorted_nums = sorted(nums)
    l, r = 0, len(nums) - 1
    while l <= r and nums[l] == sorted_nums[l]:
        l += 1
    while l <= r and nums[r] == sorted_nums[r]:
        r -= 1
    return r - l + 1
 

Approach 2:

import sys
def findUnsortedSubarray(nums):
    mi, mx = sys.maxsize, -sys.maxsize
    l, r = -1, -1
    for i, x in enumerate(nums):
        if mx > x:
            r = i
        else:
            mx = x
        if mi < nums[len(nums) - 1 - i]:
            l = len(nums) - 1 - i
        else:
            mi = nums[len(nums) - 1 - i]
    return 0 if r == -1 else r - l + 1
 

The second approach (two-pointer traversal) is generally preferred due to its better time complexity. The code examples in other languages (Java, C++, Go, TypeScript, Rust) would follow a very similar structure to these Python examples, reflecting the same algorithms.