We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Shortest Unsorted Continuous Subarray

Number: 581

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Microsoft, Meta, Goldman Sachs, LiveRamp

Problem Description

Given an integer array, the task is to find the shortest continuous subarray such that when only that subarray is sorted (in non-decreasing order), the entire array becomes sorted in non-decreasing order. If the array is already sorted, the answer is 0.

Key Insights

  • The sorted order of the array determines the positions where the actual array deviates from the sorted order.
  • A straightforward solution is to compare the array with a sorted copy and identify the first and last indices where they differ.
  • A more optimal O(n) approach involves traversing the array from left-to-right and right-to-left:
    • Left-to-right pass: Track the maximum value seen. Whenever the current number is less than this maximum, it indicates the elements are not in order; update the right boundary accordingly.
    • Right-to-left pass: Track the minimum value seen. Whenever the current number is greater than this minimum, update the left boundary.
  • If the array is already sorted, the boundaries never update, and the result is 0.
  • This approach uses constant extra space (besides a few variables), making it efficient for large inputs.

Space and Time Complexity

Time Complexity: O(n) – The array is traversed twice. Space Complexity: O(1) – Only constant extra space is used.

Solution

The solution uses a two-pointer greedy approach:

  1. In the first pass (left-to-right), track the maximum value encountered so far. When a current element is found smaller than this maximum, mark its position as a potential right boundary.
  2. In the second pass (right-to-left), track the minimum value encountered so far. When a current element is larger than this minimum, mark its position as a potential left boundary.
  3. The difference between these boundary indices (plus one) yields the length of the shortest unsorted subarray.
  4. If no such boundaries are found, then the array is already sorted, and the answer is 0.

This method avoids extra space for a sorted copy and achieves optimal time performance.

Code Solutions

# Python solution with detailed comments
def findUnsortedSubarray(nums):
    n = len(nums)
    left, right = -1, -1
    max_seen = nums[0]
    min_seen = nums[-1]
    
    # Scan from left to right to find the right boundary
    for i in range(1, n):
        max_seen = max(max_seen, nums[i])
        # if current element is less than the max seen so far, update right boundary
        if nums[i] < max_seen:
            right = i

    # Scan from right to left to find the left boundary
    for i in range(n - 2, -1, -1):
        min_seen = min(min_seen, nums[i])
        # if current element is greater than the min seen so far, update left boundary
        if nums[i] > min_seen:
            left = i
            
    # If right boundary was never updated, array is sorted.
    if right == -1:
        return 0
    return right - left + 1

# Example usage:
print(findUnsortedSubarray([2,6,4,8,10,9,15]))  # Output: 5
← Back to All Questions