LeetCode 581 - Shortest Unsorted Continuous Subarray

The problem gives an integer array nums and asks for the length of the shortest continuous subarray such that, if only that subarray is sorted in non-decreasing order, the entire array becomes sorted.

leetcodemediumarraytwo-pointersstackgreedysortingmonotonic-stack

LeetCode Problem 581

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Stack, Greedy, Sorting, Monotonic Stack

Solution

Problem Understanding

The problem gives an integer array nums and asks for the length of the shortest continuous subarray such that, if only that subarray is sorted in non-decreasing order, the entire array becomes sorted.

In other words, the array is "almost sorted", except for some misplaced elements. We need to identify the smallest contiguous section responsible for the disorder. Once that section is sorted independently, every element in the whole array should appear in non-decreasing order.

For example, consider:

[2,6,4,8,10,9,15]

The array is mostly increasing, but 6 and 4 are out of order, and 10 and 9 are also out of order. Sorting only:

[6,4,8,10,9]

produces:

[2,4,6,8,9,10,15]

which is fully sorted. The answer is therefore 5, because the subarray length is 5.

The constraints are important:

  • The array length can be as large as 10^4
  • Values may be negative
  • We are asked in the follow-up to achieve O(n) time

These constraints tell us that extremely slow approaches such as checking every possible subarray are impractical. An O(n^2) solution might barely pass depending on implementation, but anything worse is too slow. The follow-up strongly suggests there is a linear-time insight.

Several edge cases are important:

  • The array may already be sorted, in which case the answer is 0
  • The array may contain only one element
  • Duplicate values are allowed, so we must preserve non-decreasing order rather than strictly increasing order
  • The unsorted section may extend farther than the first visible inversion because misplaced elements can affect earlier or later positions

For example:

[1,3,2,2,2]

The first inversion occurs at 3 > 2, but the entire subarray [3,2,2,2] must be included because all the 2s belong before 3.

Approaches

Brute Force Approach

A straightforward way to solve the problem is to examine every possible subarray. For each candidate subarray:

  1. Copy the array
  2. Sort only that subarray
  3. Check whether the entire resulting array becomes sorted
  4. Track the minimum valid length

This approach is correct because it explicitly tests every possible continuous segment and returns the smallest one that fixes the array.

However, the runtime is extremely expensive. There are O(n^2) possible subarrays. Sorting a subarray costs up to O(n log n), and checking whether the full array is sorted costs O(n).

The total complexity becomes far too large for n = 10^4.

Optimal Approach

The key insight is that we do not actually need to simulate sorting subarrays.

Instead, we can identify which elements are "out of place".

If the array were fully sorted:

  • Every element would be greater than or equal to all elements before it
  • Every element would be less than or equal to all elements after it

We can exploit this property with two linear scans.

From left to right:

  • Track the maximum value seen so far
  • If the current element is smaller than this maximum, it is out of order
  • The right boundary of the unsorted subarray must include this position

From right to left:

  • Track the minimum value seen so far
  • If the current element is larger than this minimum, it is out of order
  • The left boundary of the unsorted subarray must include this position

This works because any element violating sorted order must belong inside the subarray that needs sorting.

Approach Time Complexity Space Complexity Notes
Brute Force O(n³ log n) O(n) Tests every subarray by sorting and validating
Optimal O(n) O(1) Uses two linear scans to find disorder boundaries

Algorithm Walkthrough

Optimal Linear Scan Algorithm

  1. Initialize two boundary variables:
  • left = -1
  • right = -1

These will eventually represent the smallest unsorted subarray. 2. Perform a left-to-right scan.

Maintain a variable max_seen, initialized to the first element.

For each index i:

  • Update max_seen = max(max_seen, nums[i])
  • If nums[i] < max_seen, then the current value is smaller than something before it, meaning it is out of order
  • Update right = i

This step finds the farthest position on the right that violates sorted order. 3. Perform a right-to-left scan.

Maintain a variable min_seen, initialized to the last element.

For each index i from right to left:

  • Update min_seen = min(min_seen, nums[i])
  • If nums[i] > min_seen, then the current value is larger than something after it, meaning it is out of order
  • Update left = i

This step finds the farthest position on the left that violates sorted order. 4. Check whether the array was already sorted.

If right == -1, then no violations were found during scanning, so return 0. 5. Otherwise, compute:

right - left + 1

This gives the length of the shortest continuous subarray that must be sorted.

Why it works

The algorithm relies on the invariant that a sorted array must maintain:

nums[i] >= max(nums[0:i])

during a left-to-right traversal, and:

nums[i] <= min(nums[i+1:])

during a right-to-left traversal.

Any element violating these conditions cannot remain in its current position in the final sorted array. Therefore, the earliest and latest violations define exactly the minimal subarray that must be sorted.

Python Solution

from typing import List

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        n = len(nums)

        left = -1
        right = -1

        max_seen = nums[0]

        for i in range(n):
            max_seen = max(max_seen, nums[i])

            if nums[i] < max_seen:
                right = i

        min_seen = nums[-1]

        for i in range(n - 1, -1, -1):
            min_seen = min(min_seen, nums[i])

            if nums[i] > min_seen:
                left = i

        if right == -1:
            return 0

        return right - left + 1

The implementation begins by initializing the array length and the boundary indices left and right.

The first loop scans from left to right while tracking the largest value encountered so far. If the current value is smaller than this maximum, then it violates sorted order because a smaller number appears after a larger one. The index is stored in right.

The second loop scans from right to left while tracking the smallest value encountered so far. If the current value is larger than this minimum, then it violates sorted order because a larger number appears before a smaller one. The index is stored in left.

If no violations are detected, the array is already sorted and the function returns 0.

Otherwise, the length of the unsorted subarray is calculated using:

right - left + 1

This corresponds exactly to the minimal continuous segment that must be sorted.

Go Solution

func findUnsortedSubarray(nums []int) int {
    n := len(nums)

    left := -1
    right := -1

    maxSeen := nums[0]

    for i := 0; i < n; i++ {
        if nums[i] > maxSeen {
            maxSeen = nums[i]
        }

        if nums[i] < maxSeen {
            right = i
        }
    }

    minSeen := nums[n-1]

    for i := n - 1; i >= 0; i-- {
        if nums[i] < minSeen {
            minSeen = nums[i]
        }

        if nums[i] > minSeen {
            left = i
        }
    }

    if right == -1 {
        return 0
    }

    return right - left + 1
}

The Go implementation follows the same logic as the Python version.

Since Go does not provide built-in max and min functions for integers, the comparisons are written explicitly with if statements.

Slices in Go naturally handle dynamic array behavior, so no additional data structures are required. Integer overflow is not a concern because the constraints are well within Go's integer range.

The algorithm uses constant extra memory and performs only two linear scans.

Worked Examples

Example 1

Input:

[2,6,4,8,10,9,15]

Left-to-Right Scan

i nums[i] max_seen nums[i] < max_seen right
0 2 2 No -1
1 6 6 No -1
2 4 6 Yes 2
3 8 8 No 2
4 10 10 No 2
5 9 10 Yes 5
6 15 15 No 5

Final right = 5.

Right-to-Left Scan

i nums[i] min_seen nums[i] > min_seen left
6 15 15 No -1
5 9 9 No -1
4 10 9 Yes 4
3 8 8 No 4
2 4 4 No 4
1 6 4 Yes 1
0 2 2 No 1

Final answer:

5 - 1 + 1 = 5

Example 2

Input:

[1,2,3,4]

Left-to-Right Scan

No element is smaller than max_seen.

right = -1

Since no disorder exists, the array is already sorted.

Answer:

0

Example 3

Input:

[1]

Single-element arrays are always sorted.

No violations occur in either scan.

Answer:

0

Complexity Analysis

Measure Complexity Explanation
Time O(n) Two linear scans across the array
Space O(1) Only a few variables are used

The algorithm processes the array twice, once from left to right and once from right to left. Each scan touches every element exactly once, resulting in linear runtime.

No auxiliary arrays, stacks, or sorting operations are used. Only a constant number of variables are maintained, so the space complexity remains constant.

Test Cases

sol = Solution()

assert sol.findUnsortedSubarray([2,6,4,8,10,9,15]) == 5  # standard unsorted middle section
assert sol.findUnsortedSubarray([1,2,3,4]) == 0  # already sorted
assert sol.findUnsortedSubarray([1]) == 0  # single element
assert sol.findUnsortedSubarray([1,3,2,2,2]) == 4  # duplicates inside disorder
assert sol.findUnsortedSubarray([2,1]) == 2  # entire array unsorted
assert sol.findUnsortedSubarray([1,2,4,5,3]) == 3  # unsorted tail element
assert sol.findUnsortedSubarray([5,4,3,2,1]) == 5  # fully reversed
assert sol.findUnsortedSubarray([1,2,3,3,3]) == 0  # duplicates but sorted
assert sol.findUnsortedSubarray([1,2,3,3,2,2]) == 4  # duplicate boundary issue
assert sol.findUnsortedSubarray([-1,-2,-3,-4]) == 4  # negative numbers
assert sol.findUnsortedSubarray([1,2,4,3,5]) == 2  # small middle inversion
assert sol.findUnsortedSubarray([1,1,1,1]) == 0  # all equal values
Test Why
[2,6,4,8,10,9,15] Standard example with middle disorder
[1,2,3,4] Already sorted array
[1] Smallest valid input
[1,3,2,2,2] Duplicates interacting with inversion
[2,1] Entire array must be sorted
[1,2,4,5,3] Disorder near the end
[5,4,3,2,1] Fully descending array
[1,2,3,3,3] Duplicates in sorted order
[1,2,3,3,2,2] Duplicate-heavy unsorted section
[-1,-2,-3,-4] Negative number handling
[1,2,4,3,5] Minimal unsorted middle
[1,1,1,1] All equal values

Edge Cases

Already Sorted Array

An already sorted array is one of the most important edge cases because many implementations accidentally return a positive length.

Example:

[1,2,3,4]

During the left-to-right scan, no element is ever smaller than max_seen, so right remains -1. The implementation explicitly checks this condition and returns 0.

Arrays with Duplicates

Duplicates can easily introduce off-by-one errors if the implementation assumes strictly increasing order.

Example:

[1,3,2,2,2]

The 3 must move after all the 2s, so the unsorted region extends farther than the first inversion. The algorithm correctly handles this because it uses:

nums[i] < max_seen

and:

nums[i] > min_seen

rather than strict ordering assumptions.

Entire Array Unsorted

Some arrays require sorting every element.

Example:

[5,4,3,2,1]

Every element violates sorted order during both scans. The algorithm expands the boundaries to include the full range, correctly returning the array length.

Single Element Arrays

A single element is trivially sorted.

Example:

[1]

Both scans execute safely because the implementation initializes from valid indices and performs no invalid accesses. Since no violations occur, the function correctly returns 0.