Shortest Unsorted Continuous Subarray

medium array two pointers monotonic stack

Problem

Given an integer array nums, find the length of the shortest contiguous subarray such that sorting that subarray alone makes the whole array non-decreasing. Return 0 if it is already sorted.

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

Output5

Sort [6, 4, 8, 10, 9] to make the whole array sorted.

nums (comma-separated)

def find_unsorted_subarray(nums):
    n = len(nums)
    right = -1
    cur_max = float('-inf')
    for i in range(n):
        if nums[i] < cur_max:
            right = i
        else:
            cur_max = nums[i]
    left = 0
    cur_min = float('inf')
    for i in range(n - 1, -1, -1):
        if nums[i] > cur_min:
            left = i
        else:
            cur_min = nums[i]
    return 0 if right == -1 else right - left + 1

function findUnsortedSubarray(nums) {
  const n = nums.length;
  let right = -1, max = -Infinity;
  for (let i = 0; i < n; i++) {
    if (nums[i] < max) right = i;
    else max = nums[i];
  }
  let left = 0, min = Infinity;
  for (let i = n - 1; i >= 0; i--) {
    if (nums[i] > min) left = i;
    else min = nums[i];
  }
  return right === -1 ? 0 : right - left + 1;
}

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length, right = -1, max = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            if (nums[i] < max) right = i;
            else max = nums[i];
        }
        int left = 0, min = Integer.MAX_VALUE;
        for (int i = n - 1; i >= 0; i--) {
            if (nums[i] > min) left = i;
            else min = nums[i];
        }
        return right == -1 ? 0 : right - left + 1;
    }
}

int findUnsortedSubarray(vector<int>& nums) {
    int n = nums.size(), right = -1, maxv = INT_MIN;
    for (int i = 0; i < n; i++) {
        if (nums[i] < maxv) right = i;
        else maxv = nums[i];
    }
    int left = 0, minv = INT_MAX;
    for (int i = n - 1; i >= 0; i--) {
        if (nums[i] > minv) left = i;
        else minv = nums[i];
    }
    return right == -1 ? 0 : right - left + 1;
}

Explanation

We want the shortest middle chunk that, if sorted alone, makes the whole array non-decreasing. The smart approach finds the right and left edges of that chunk with two running-extreme sweeps — no sorting needed.

In the forward sweep we track cur_max, the largest value seen so far. Any element smaller than cur_max is out of place, so it must lie inside the messy region; the last such index becomes right. Intuitively, everything to the right of a properly sorted prefix should be at least as big as the max behind it.

In the backward sweep we track cur_min, the smallest value seen from the right. Any element bigger than cur_min is out of place; the last such index (scanning leftward) becomes left. The answer is the span right - left + 1, or 0 if no violations were found (already sorted).

Example: nums = [2, 6, 4, 8, 10, 9, 15]. The forward sweep flags right = 5 (the 9); the backward sweep flags left = 1 (the 6). The subarray [6, 4, 8, 10, 9] has length 5 - 1 + 1 = 5.

Both sweeps are linear and use only a few variables, so the whole solution is O(n) time and O(1) space.

Time: O(n) Space: O(1)