Shortest Unsorted Continuous Subarray: Finding the Minimum Slice to Sort

LeetCode 581, Shortest Unsorted Continuous Subarray, asks you to find the shortest subarray that, if sorted, would make the entire array sorted. You need to return the length of that subarray.

At first glance you might think you need to actually sort the array and compare. That works, but it costs O(n log n). There is a cleaner O(n) approach that finds the boundaries of the unsorted region by scanning from both ends.

The problem

Given an integer array nums, find one continuous subarray such that if you only sort this subarray in non-decreasing order, the whole array becomes sorted. Return the length of the shortest such subarray.

• nums = [2,6,4,8,10,9,15] returns 5 because sorting [6,4,8,10,9] makes the whole array [2,4,6,8,9,10,15].
• nums = [1,2,3,4] returns 0 because the array is already sorted.
• nums = [1] returns 0.

The approach

The brute force way is to sort a copy of the array, then compare each position to find where the original and sorted versions first and last differ. That gives you the boundaries of the unsorted subarray. It works, but sorting costs O(n log n).

The O(n) insight comes from thinking about what it means for an element to be "out of place." If you scan left to right and track the maximum value seen so far, any element that is smaller than the current max must be part of the unsorted region. The last such element gives you the right boundary.

Similarly, if you scan right to left and track the minimum value seen so far, any element that is larger than the current min must be part of the unsorted region. The last such element gives you the left boundary.

The solution

def findUnsortedSubarray(nums):
    n = len(nums)
    right = -1
    left = -1
    max_so_far = nums[0]
    min_so_far = nums[n - 1]

    for i in range(1, n):
        if nums[i] < max_so_far:
            right = i
        else:
            max_so_far = nums[i]

    for i in range(n - 2, -1, -1):
        if nums[i] > min_so_far:
            left = i
        else:
            min_so_far = nums[i]

    if right == -1:
        return 0

    return right - left + 1

Here is what each part does:

1. Initialize right and left to -1. If they stay at -1, the array is already sorted.
2. Scan left to right, tracking max_so_far. Whenever nums[i] is less than max_so_far, that element is out of place, so update right = i.
3. Scan right to left, tracking min_so_far. Whenever nums[i] is greater than min_so_far, that element is out of place, so update left = i.
4. If right is still -1, the array was already sorted. Return 0.
5. Otherwise, return right - left + 1.

Step-by-step walkthrough

Let's trace through nums = [2, 6, 4, 8, 10, 9, 15]. The left-to-right scan finds the rightmost out-of-place element, and the right-to-left scan finds the leftmost one.

The two scans together pinpoint the exact boundaries: left=1 and right=5. The answer is 5 - 1 + 1 = 5.

Complexity analysis

Time: O(n). Two linear scans through the array. Each scan visits every element exactly once.

Space: O(1). Only a handful of variables (left, right, max_so_far, min_so_far) regardless of input size.

The two-pass approach is strictly better in both time and space.

The building blocks

This problem decomposes into two reusable techniques that CodeBricks drills independently:

1. Forward scan with running max

Scanning left to right while maintaining the maximum value seen so far is a pattern that appears in many array problems. In this problem, the running max tells you whether the current element violates sorted order. If nums[i] is less than the max of everything before it, it cannot stay in its current position.

max_so_far = nums[0]
for i in range(1, n):
    if nums[i] < max_so_far:
        right = i
    else:
        max_so_far = nums[i]

This same running-max pattern shows up in Best Time to Buy and Sell Stock (tracking max profit), Jump Game (tracking max reachable index), and Trapping Rain Water (tracking left max heights).

2. Backward scan with running min

The mirror image: scanning right to left while maintaining the minimum value seen so far. Any element greater than the minimum of everything to its right is out of place.

min_so_far = nums[n - 1]
for i in range(n - 2, -1, -1):
    if nums[i] > min_so_far:
        left = i
    else:
        min_so_far = nums[i]

Combining forward and backward passes to solve a problem in O(n) is a technique you also see in Product of Array Except Self (prefix and suffix products) and Candy (forward and backward greedy passes).

Edge cases

Before submitting, verify your solution handles:

• Already sorted: [1, 2, 3, 4, 5]. Both scans find no violations. right stays at -1. Return 0.
• Reverse sorted: [5, 4, 3, 2, 1]. Every element is a violation in both scans. left=0, right=4. Return 5.
• Single element: [1]. The loops do not execute. Return 0.
• Two elements, sorted: [1, 2]. No violations. Return 0.
• Two elements, unsorted: [2, 1]. right=1, left=0. Return 2.
• Duplicates: [1, 3, 2, 2, 2]. The max scan catches index 2, 3, 4 (all are <= 3). The min scan catches index 1 (3 > 2). Return 4.
• Unsorted only at the ends: [2, 1] or [1, 3, 2]. The scans correctly find the minimal boundaries.

From understanding to recall

Reading through this solution, the logic feels natural. But in an interview, you need to recall two specific decisions: scan left to right tracking max for the right boundary, and scan right to left tracking min for the left boundary. Getting the direction and the comparison flipped even once gives a wrong answer. Spaced repetition drills these details into muscle memory, so the forward-max-backward-min pattern becomes automatic rather than something you reconstruct under pressure.

Related posts

• Sort Colors - Another array sorting problem that uses clever pointer manipulation instead of a full sort
• Find Minimum in Rotated Sorted Array - Finding where sorted order breaks, a related concept
• Wiggle Sort II - Another problem about array ordering that avoids a naive sort approach

Each of these problems works around sorting constraints using targeted scans and pointer logic. Once you see how forward and backward passes detect boundaries here, the same two-pass thinking unlocks solutions for many other array problems.