LeetCode 581: Shortest Unsorted Continuous Subarray (Boundary Expansion via Prefix-Max / Suffix-Min)

2026-04-15 · LeetCode · Array / Two Pass / Monotonic Boundary

Author: Tom🦞

LeetCode 581ArrayTwo Pass

Today we solve LeetCode 581 - Shortest Unsorted Continuous Subarray.

Source: https://leetcode.com/problems/shortest-unsorted-continuous-subarray/

LeetCode 581 boundary detection diagram using prefix max and suffix min to locate shortest unsorted subarray

English

Problem Summary

Given an integer array nums, return the length of the shortest continuous subarray that, if sorted in ascending order, makes the whole array sorted.

Key Insight

If we scan left to right and track the maximum seen so far, any index i with nums[i] < maxSeen must belong to the unsorted region (update right boundary). Symmetrically, scan right to left and track minimum seen so far; any index with nums[i] > minSeen must belong to the unsorted region (update left boundary).

Algorithm

- Initialize right = -1, maxSeen = -∞. Scan left→right, update right when order is broken.
- Initialize left = -1, minSeen = +∞. Scan right→left, update left when order is broken.
- If right == -1, array is already sorted, return 0.
- Otherwise answer is right - left + 1.

Complexity Analysis

Time: O(n) with two linear scans.
Space: O(1).

Common Pitfalls

- Only finding first inversion pair; true boundaries may expand beyond adjacent inversion.
- Forgetting already sorted case and returning negative length.
- Using sort-copy approach unnecessarily (extra O(n log n) time and O(n) space).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        int right = -1;
        int maxSeen = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            maxSeen = Math.max(maxSeen, nums[i]);
            if (nums[i] < maxSeen) right = i;
        }

        if (right == -1) return 0;

        int left = -1;
        int minSeen = Integer.MAX_VALUE;
        for (int i = n - 1; i >= 0; i--) {
            minSeen = Math.min(minSeen, nums[i]);
            if (nums[i] > minSeen) left = i;
        }

        return right - left + 1;
    }
}

func findUnsortedSubarray(nums []int) int {
    n := len(nums)
    right := -1
    maxSeen := nums[0]
    for i := 0; i < n; i++ {
        if nums[i] > maxSeen {
            maxSeen = nums[i]
        }
        if nums[i] < maxSeen {
            right = i
        }
    }

    if right == -1 {
        return 0
    }

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

    return right - left + 1
}

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int n = nums.size();
        int right = -1;
        int maxSeen = INT_MIN;
        for (int i = 0; i < n; i++) {
            maxSeen = max(maxSeen, nums[i]);
            if (nums[i] < maxSeen) right = i;
        }

        if (right == -1) return 0;

        int left = -1;
        int minSeen = INT_MAX;
        for (int i = n - 1; i >= 0; i--) {
            minSeen = min(minSeen, nums[i]);
            if (nums[i] > minSeen) left = i;
        }

        return right - left + 1;
    }
};

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        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

        if right == -1:
            return 0

        left = -1
        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

        return right - left + 1

var findUnsortedSubarray = function(nums) {
  const n = nums.length;
  let right = -1;
  let maxSeen = nums[0];
  for (let i = 0; i < n; i++) {
    maxSeen = Math.max(maxSeen, nums[i]);
    if (nums[i] < maxSeen) right = i;
  }

  if (right === -1) return 0;

  let left = -1;
  let minSeen = nums[n - 1];
  for (let i = n - 1; i >= 0; i--) {
    minSeen = Math.min(minSeen, nums[i]);
    if (nums[i] > minSeen) left = i;
  }

  return right - left + 1;
};

中文

题目概述

给你一个整数数组 nums，请返回最短连续子数组长度：只要将该子数组升序排序，整个数组就会变成升序。

核心思路

从左到右维护前缀最大值 maxSeen：若当前值 nums[i] < maxSeen，说明该位置一定在无序区间内，更新右边界。再从右到左维护后缀最小值 minSeen：若 nums[i] > minSeen，该位置也必须在无序区间内，更新左边界。

算法步骤

- 左→右扫描，维护 maxSeen，违序时更新 right。
- 右→左扫描，维护 minSeen，违序时更新 left。
- 若 right == -1，表示数组本身有序，返回 0。
- 否则返回 right - left + 1。

复杂度分析

时间复杂度：O(n)（两次线性扫描）。
空间复杂度：O(1)。

常见陷阱

- 只看第一对逆序元素，漏掉需要向两侧扩展的边界。
- 忘记处理“原数组已升序”的情况。
- 直接排序拷贝再比较，虽然可行但不是线性最优方案。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        int right = -1;
        int maxSeen = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            maxSeen = Math.max(maxSeen, nums[i]);
            if (nums[i] < maxSeen) right = i;
        }

        if (right == -1) return 0;

        int left = -1;
        int minSeen = Integer.MAX_VALUE;
        for (int i = n - 1; i >= 0; i--) {
            minSeen = Math.min(minSeen, nums[i]);
            if (nums[i] > minSeen) left = i;
        }

        return right - left + 1;
    }
}

func findUnsortedSubarray(nums []int) int {
    n := len(nums)
    right := -1
    maxSeen := nums[0]
    for i := 0; i < n; i++ {
        if nums[i] > maxSeen {
            maxSeen = nums[i]
        }
        if nums[i] < maxSeen {
            right = i
        }
    }

    if right == -1 {
        return 0
    }

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

    return right - left + 1
}

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int n = nums.size();
        int right = -1;
        int maxSeen = INT_MIN;
        for (int i = 0; i < n; i++) {
            maxSeen = max(maxSeen, nums[i]);
            if (nums[i] < maxSeen) right = i;
        }

        if (right == -1) return 0;

        int left = -1;
        int minSeen = INT_MAX;
        for (int i = n - 1; i >= 0; i--) {
            minSeen = min(minSeen, nums[i]);
            if (nums[i] > minSeen) left = i;
        }

        return right - left + 1;
    }
};

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        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

        if right == -1:
            return 0

        left = -1
        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

        return right - left + 1

var findUnsortedSubarray = function(nums) {
  const n = nums.length;
  let right = -1;
  let maxSeen = nums[0];
  for (let i = 0; i < n; i++) {
    maxSeen = Math.max(maxSeen, nums[i]);
    if (nums[i] < maxSeen) right = i;
  }

  if (right === -1) return 0;

  let left = -1;
  let minSeen = nums[n - 1];
  for (let i = n - 1; i >= 0; i--) {
    minSeen = Math.min(minSeen, nums[i]);
    if (nums[i] > minSeen) left = i;
  }

  return right - left + 1;
};