Shortest Unsorted Continuous Subarray — O(n) One-Pass Explained [Amazon, Google]

Problem Statement#

Given an integer array nums, find the smallest subarray that, if you sort that subarray in ascending order, makes the whole array sorted. Return the length of that subarray.

Examples:

Input:  [2, 6, 4, 8, 10, 9, 15]
Output: 5
Reason: Sorting the subarray [6, 4, 8, 10, 9] (indices 1–5) gives [2, 4, 6, 8, 9, 10, 15]
 
Input:  [1, 2, 3, 4, 5]
Output: 0
Reason: Already sorted — no subarray needs to be touched
 
Input:  [1]
Output: 0
Reason: Single element is trivially sorted

Constraints: 1 <= nums.length <= 10^4, -10^5 <= nums[i] <= 10^5

Why This Problem Matters#

LeetCode 581 is a medium-difficulty problem that appears regularly in Amazon and Google phone screens. On the surface it looks like a simple sorting question — and that naive reading is exactly the trap. The O(n log n) sort-and-compare approach works, but every competitive candidate knows it. What separates you from the pack is the O(n) single-pass solution, which requires a genuinely clever insight about where an unsorted region begins and ends.

Interview frequency: Amazon is the most frequent asker of this problem. It regularly appears in online assessments and first-round technical screens. Google uses it as a warm-up to probe whether a candidate thinks about algorithmic complexity naturally or reaches for the easy answer.

Why it matters beyond this problem: The underlying technique — tracking a running extremum and checking for violations — is a building block that appears in problems like "verify preorder sequence in BST", "find the minimum in rotated sorted array", and any problem where you need to detect where a sorted invariant breaks down.

Even if you never see this exact problem in an interview, the mental discipline of asking "where does the sorted order break, and what does that imply about the boundaries?" is invaluable.

The O(n) One-Pass Insight#

The sorting approach is intuitive but asks you to do extra work: sort a copy, then find where the two arrays diverge. Can you find those boundaries without sorting?

Yes — and the key observation is this:

Any element that is out of place must be smaller than the maximum of everything to its left, or larger than the minimum of everything to its right.

Think about it. In a correctly sorted array, every element is at least as large as everything before it and at most as small as everything after it. If an element violates either rule, it is inside the unsorted region.

This gives us a two-scan strategy:

Left-to-right scan — find the right boundary: Walk left to right, tracking the running maximum so far. Any element that is smaller than the running maximum is out of place — it should have appeared before the maximum. The last such element is the right boundary of the unsorted region.

Right-to-left scan — find the left boundary: Walk right to left, tracking the running minimum so far. Any element that is larger than the running minimum is out of place — it should have appeared after the minimum. The last such element (furthest left) is the left boundary.

Why this correctly identifies the minimal subarray:

• Everything to the left of the left boundary is already in its correct final position: it is smaller than all elements in the subarray and in the correct sorted order.
• Everything to the right of the right boundary is already in its correct final position: it is larger than all elements in the subarray and in the correct sorted order.
• The subarray between the two boundaries contains all the violations and must be sorted as a unit.

If no violations are found in either scan, the array is already sorted and the answer is 0. The initialization trick left = -1, right = -2 makes right - left + 1 = -2 - (-1) + 1 = 0 handle this cleanly without a special case.

Visual Dry Run#

Let us trace through the canonical example [2, 6, 4, 8, 10, 9, 15] step by step.

Left-to-right pass — tracking running max, flagging right boundary:

After left-to-right: right = 5

Right-to-left pass — tracking running min, flagging left boundary:

After right-to-left: left = 1

Result: right - left + 1 = 5 - 1 + 1 = 5

The subarray is indices 1 through 5: [6, 4, 8, 10, 9]. Sort it to get [4, 6, 8, 9, 10], and the full array becomes [2, 4, 6, 8, 9, 10, 15]. Correct.

Edge case — already sorted [1, 2, 3, 4, 5]:

Left-to-right: running max always equals nums[i], so right stays at -2. Right-to-left: running min always equals nums[i], so left stays at -1. Result: right - left + 1 = -2 - (-1) + 1 = 0. Correct, no special case needed.

Common Mistakes#

Mistake 1 — Sorting and comparing without knowing why#

Many candidates sort the original array and then find where the sorted and original arrays diverge:

# Works but O(n log n) — interviewer will ask for O(n)
sorted_nums = sorted(nums)
left = right = 0
for i in range(len(nums)):
    if nums[i] != sorted_nums[i]:
        left = i
        break
for i in range(len(nums) - 1, -1, -1):
    if nums[i] != sorted_nums[i]:
        right = i
        break
return right - left + 1 if right > left else 0

This is correct, but it costs O(n log n) time and O(n) space. The interviewer will almost certainly follow up with "Can you do it in O(n) time and O(1) space?" Know this solution exists, state it immediately, but pivot straight to the one-pass approach.

Mistake 2 — Only scanning in one direction#

A common incomplete approach is to scan left-to-right to find where the array stops being non-decreasing, and right-to-left to find where it stops being non-increasing, then returning the length between those two points. This finds where the first descent begins and the last ascent ends — but it does not correctly account for elements outside those raw boundaries that still need to be included.

Example: [1, 3, 2, 2, 2]. A naive "first descent / last ascent" scan sets left at index 1 (where 3 > 2) and right at index 4. But with the proper running-max/running-min approach, the right boundary is confirmed at index 4, and the left boundary is confirmed at index 1. In this case they agree — but for something like [2, 3, 3, 2, 4], the naive approach may misplace the left boundary at index 0 instead of index 0 (which is actually correct here), while a subtly wrong implementation would get index 1. The running extremum approach is the only provably correct O(n) method.

Mistake 3 — Forgetting the initialization trick for the already-sorted case#

If you initialize left = 0 and right = 0 (or both to 0), then when the array is already sorted and no violations are found, you return right - left + 1 = 1 instead of 0 — a classic off-by-one bug.

The correct initialization is left = -1 and right = -2, so that when no violations occur, right - left + 1 = -2 - (-1) + 1 = 0. Some implementations handle this with an explicit check at the end (return 0 if right < left else right - left + 1), which is also fine but adds a branch.

Mistake 4 — Confusing left/right scan directions#

The right boundary is found by the left-to-right scan (tracking the running maximum). The left boundary is found by the right-to-left scan (tracking the running minimum). It is easy to swap these in an interview. A quick way to remember: you are looking for the rightmost element that is "too small" (it violates the max from its left), and the leftmost element that is "too large" (it violates the min from its right).

Solutions#

Approach 1 — Sort and Compare — O(n log n) time, O(n) space#

State this first to show you understand the problem, then immediately offer the optimal version.

Python:

from typing import List
 
class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        # Create a sorted copy for comparison
        sorted_nums = sorted(nums)
        
        n = len(nums)
        left, right = 0, n - 1
        
        # Move left pointer right until we find a mismatch
        while left < n and nums[left] == sorted_nums[left]:
            left += 1
        
        # Array is already sorted — no subarray needed
        if left == n:
            return 0
        
        # Move right pointer left until we find a mismatch
        while nums[right] == sorted_nums[right]:
            right -= 1
        
        # Length of the subarray that needs sorting
        return right - left + 1

JavaScript:

function findUnsortedSubarray(nums) {
    // Create a sorted copy for comparison
    const sortedNums = [...nums].sort((a, b) => a - b);
    
    const n = nums.length;
    let left = 0;
    let right = n - 1;
    
    // Move left pointer right until we find a mismatch
    while (left < n && nums[left] === sortedNums[left]) {
        left++;
    }
    
    // Array is already sorted — no subarray needed
    if (left === n) return 0;
    
    // Move right pointer left until we find a mismatch
    while (nums[right] === sortedNums[right]) {
        right--;
    }
    
    // Length of the subarray that needs sorting
    return right - left + 1;
}

Approach 2 — O(n) One-Pass with Running Extrema — Optimal#

This is the solution your interviewer is hoping you will arrive at. Two passes, O(1) space, no sorting.

Python:

from typing import List
 
class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        
        # Initialize boundaries to produce length 0 when no violations found:
        # right - left + 1 = -2 - (-1) + 1 = 0
        left = -1
        right = -2
        
        # Track the running maximum from the left and running minimum from the right
        max_val = nums[0]   # largest element seen so far (left-to-right)
        min_val = nums[-1]  # smallest element seen so far (right-to-left)
        
        for i in range(1, n):
            # Left-to-right pass: update running max
            max_val = max(max_val, nums[i])
            
            # If this element is smaller than the running max,
            # it is out of place — update the right boundary
            if nums[i] < max_val:
                right = i
        
        for i in range(n - 2, -1, -1):
            # Right-to-left pass: update running min
            min_val = min(min_val, nums[i])
            
            # If this element is larger than the running min,
            # it is out of place — update the left boundary
            if nums[i] > min_val:
                left = i
        
        # Length formula works for both 0 and positive results
        return right - left + 1

JavaScript:

function findUnsortedSubarray(nums) {
    const n = nums.length;
    
    // Initialize boundaries to produce length 0 when no violations found:
    // right - left + 1 = -2 - (-1) + 1 = 0
    let left = -1;
    let right = -2;
    
    // Track running max (left-to-right) and running min (right-to-left)
    let maxVal = nums[0];      // largest element seen scanning left-to-right
    let minVal = nums[n - 1];  // smallest element seen scanning right-to-left
    
    for (let i = 1; i < n; i++) {
        // Update running maximum as we scan left-to-right
        maxVal = Math.max(maxVal, nums[i]);
        
        // If this element is smaller than the running max,
        // it is displaced — record it as the new right boundary
        if (nums[i] < maxVal) {
            right = i;
        }
    }
    
    for (let i = n - 2; i >= 0; i--) {
        // Update running minimum as we scan right-to-left
        minVal = Math.min(minVal, nums[i]);
        
        // If this element is larger than the running min,
        // it is displaced — record it as the new left boundary
        if (nums[i] > minVal) {
            left = i;
        }
    }
    
    // Returns 0 when array is already sorted (right < left)
    return right - left + 1;
}

Complexity Analysis#

The one-pass solution dominates on both axes — strictly better time complexity and strictly better space complexity. In an interview, state the sort approach to demonstrate clarity of thought, then derive the O(n) approach to demonstrate depth.

Follow-up Questions#

1. What if the array has duplicates?#

The same algorithm handles duplicates correctly because the violation condition uses strict inequalities (nums[i] < max_val and nums[i] > min_val). Equal elements do not trigger a boundary update, which is correct — two equal adjacent elements do not break the sorted order.

Test case: [1, 3, 2, 2, 2] Left-to-right: max becomes 3 at index 1; index 2 (value 2) triggers right = 2, index 3 (value 2) triggers right = 3, index 4 (value 2) triggers right = 4. So right = 4. Right-to-left: min stays 2; index 1 (value 3) triggers left = 1. So left = 1. Answer: 4 - 1 + 1 = 4. Sorting [3, 2, 2, 2] gives [1, 2, 2, 2, 3]. Correct.

2. Return the actual subarray, not just its length#

The indices left and right from the one-pass solution are exactly the start and end of the subarray. Return nums[left:right+1] (Python) or nums.slice(left, right + 1) (JavaScript). If right < left, return an empty array.

3. Can you do a single pass instead of two?#

You can combine both scans into one pass, but it requires forward and backward scanning simultaneously (or using a deque), which complicates the code without improving asymptotic complexity. The two-pass version is preferred for clarity in interviews.

4. What if the array is sorted in descending order?#

The entire array is the answer: n (length of the whole array). The algorithm handles this correctly — the right boundary reaches the last index and the left boundary reaches index 0.

5. How does this relate to "count of smaller numbers after self" (LeetCode 315)?#

Both problems rely on detecting elements that are displaced relative to a running extremum. LeetCode 315 asks for the count of displaced elements per position using a more sophisticated data structure (BIT or merge sort), whereas this problem only needs the boundary of the displaced region.

This Pattern Solves#

The running-extremum-plus-violation-check pattern appears across many problems:

Whenever a problem asks you to find a contiguous region where a sorted or monotonic invariant breaks down, reach for this pattern first.

Key Takeaways#

• Scan left-to-right tracking the running maximum; any element smaller than the running max is out of place — its index is the rightmost boundary of the unsorted subarray.
• Scan right-to-left tracking the running minimum; any element larger than the running min is out of place — its index is the leftmost boundary.
• Initialize left = -1, right = -2; the length formula right - left + 1 naturally returns 0 when no violations exist (already sorted).
• O(n) time, O(1) space — no sorting, no extra arrays.
• The sort-and-compare O(n log n) approach is a valid starting point to mention, but the interviewer expects you to reach O(n).
• Edge cases: duplicates are handled correctly (equal values do not violate order); all-same arrays return 0; single-element arrays return 0.
• The same "track running extremum, flag violations" pattern solves: Verify Preorder BST (LC 255), Jump Game (LC 55), and Maximum Width Ramp (LC 962).