Domain 2MediumCORE

Shortest Unsorted Continuous Subarray

We are given an integer array nums. The goal is to identify the smallest continuous subarray such that if we sort only this specific portion of the array in ascending order, the entire original array becomes sorted. We need to return the length of this shortest unsorted subarray. If the array is already sorted or contains a single element, the result should be 0.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Array

581. Shortest Unsorted Continuous Subarray

Model: qwen3.5:9b
Topics: Array
FAANG asked: 1
Acceptance rate: 32.9%


Problem Breakdown

We are given an integer array nums. The goal is to identify the smallest continuous subarray such that if we sort only this specific portion of the array in ascending order, the entire original array becomes sorted. We need to return the length of this shortest unsorted subarray. If the array is already sorted or contains a single element, the result should be 0.

Inputs: An integer list nums (length up to 10410^4). Outputs: A single integer representing the length of the required subarray. Constraints & Edge Cases:

  • Empty/Single Element: Constraints say length ≥1\ge 1. For a single element or an array that is naturally sorted, we should return 0.
  • Duplicates: Arrays like [1, 3, 2, 4, 5, 6, 7] vs [1, 3, 2, 2, 4]. The logic must handle equal values correctly (non-decreasing order).
  • Negative Numbers: Values can be negative; comparisons hold standardly.

Intuition

A brute-force approach would involve checking every possible subarray by sorting it and verifying if the whole array becomes sorted. This is computationally expensive (O(N3)O(N^3) or at best O(N2log⁡N)O(N^2 \log N)), which will time out given constraints of N=104N=10^4.

We need to identify exactly where the disorder begins and ends without resorting to sorting repeatedly. The key observation is that any element in a sorted array must be greater than all elements preceding it (from its left) and smaller than all elements succeeding it (to its right). Specifically:

  1. Left Boundary: We need to find the first index from the left where an element violates the non-decreasing order relative to what appears later in the array? No, simpler: The unsorted subarray must include any number that is smaller than a maximum value appearing before it (from the left).
  2. Right Boundary: Similarly, we need to find the last index from the right where an element violates non-decreasing order relative to what appears earlier in the array? No: The unsorted subarray must include any number that is larger than a minimum value appearing after it (from the right).

So, if we traverse left-to-right and keep track of the maximum seen so far (max_val), whenever nums[i] < max_val, index i must be part of our unsorted subarray because there exists a larger element before it that needs to move past this position. We update the right boundary (end) to include these violations. Conversely, traversing right-to-left with a minimum seen so far (min_val), whenever nums[i] > min_val, index i must be part of our subarray because there is a smaller element after it that needs to move past this position. We update the left boundary (start).

Approach

We will use two linear passes over the array, maintaining constant space complexity (O(1)O(1)).

Pass 1 (Left-to-Right): Initialize max_val with the first element and a variable for the rightmost violation index. Iterate through the array. If we encounter an element smaller than our running maximum (nums[i] < max_val), it means this position is out of order relative to something before it. We update the end boundary (end) to i.

Pass 2 (Right-to-Left): Initialize min_val with the last element and a variable for the leftmost violation index. Iterate backwards. If we encounter an element larger than our running minimum (nums[i] > min_val), it means this position is out of order relative to something after it. We update the start boundary (start) to i.

Final Calculation: If no violations were found (e.g., array was already sorted), return 0. Otherwise, calculate length as end - start + 1. Note that we must initialize boundaries carefully; if a violation is never detected in either pass, the result should be treated as “already sorted”.

Complexity Analysis

  • Time: O(N)O(N). We traverse the array twice (once forward, once backward). Each operation inside loops is constant time.
  • Space: O(1)O(1). We only use a few integer variables for tracking boundaries and running min/max values. No additional data structures are required.

Solution

def findUnsortedSubarray(nums):
    n = len(nums)
    
    # Initialize start and end to -1 to indicate no unsorted subarray found yet
    start, end = -1, -1
    
    # Pass 1: Left to Right -> Find the rightmost boundary of unsorted subarray
    max_val = nums[0]
    for i in range(1, n):
        if nums[i] < max_val:
            end = i
        
        # Always update max_val seen so far
        max_val = max(max_val, nums[i])

    # Pass 2: Right to Left -> Find the leftmost boundary of unsorted subarray
    min_val = nums[-1]
    for i in range(n - 2, -1, -1):
        if nums[i] > min_val:
            start = i
            
        # Always update min_val seen so far
        min_val = min(min_val, nums[i])

    # If no violations were found (start remains -1), the array is already sorted.
    return end - start + 1 if start != -1 else 0

Edge Cases Handled

  • Already Sorted Array: The end variable remains -1 in the first pass because no element is smaller than a preceding maximum. Similarly, start remains -1. We check this condition and return 0.
  • Single Element / Empty (Constraint ≥1\ge 1): Loop ranges handle single elements gracefully; logic returns 0 if boundaries aren’t set.
  • Reverse Sorted: Every element triggers a violation in both passes, correctly identifying the entire array as the subarray to sort.
  • Duplicates: The comparisons (<, >) strictly enforce order violations. Equal values do not trigger boundary updates unless they violate strict ordering relative to min/max seen (which is correct for non-decreasing requirement).