Shortest Unsorted Continuous Subarray — Solution

Problem

Given an array of integers, find the length of the shortest contiguous subarray that, when sorted in ascending order, makes the entire array sorted. If the array is already sorted, return 0.

• Input: nums = [2, 6, 4, 8, 10, 9, 15]
• Output: 5
• Explanation: Sorting nums[1..5] — the subarray [6, 4, 8, 10, 9] — produces [2, 4, 6, 8, 9, 10, 15].

A counter-example: [1, 2, 3, 4, 5] returns 0 because the array is already sorted and no subarray needs to change.

Intuition

The "dirty" subarray is the region where elements are out of place relative to their neighbors. Scanning left to right, any element that falls below the maximum seen so far is in the wrong position — it must be inside the subarray we need to sort, so the right boundary is the last such element. The same logic applied from right to left with a running minimum gives the left boundary. Two linear scans with no extra memory produce the exact answer without sorting.

Approach 1 — Sort and Compare

Sort a copy of the array, then find the first and last positions where the original and sorted versions disagree. Everything between those positions is the subarray that must be sorted.

1. Create a sorted copy of the input array.
2. Scan left to right to find the first index where the two arrays differ — this is the left boundary.
3. If no difference exists, return 0 (already sorted).
4. Scan right to left to find the last index where the two arrays differ — this is the right boundary.
5. Return right_boundary - left_boundary + 1.

1class Solution:
2    def findUnsortedSubarray(self, nums: List[int]) -> int:
3        sorted_nums = sorted(nums)
4
5        left_boundary = 0
6        while left_boundary < len(nums) and nums[left_boundary] == sorted_nums[left_boundary]:
7            left_boundary += 1
8
9        if left_boundary == len(nums):
10            return 0  # every element matched; array is already sorted
11
12        right_boundary = len(nums) - 1
13        while nums[right_boundary] == sorted_nums[right_boundary]:
14            right_boundary -= 1
15
16        return right_boundary - left_boundary + 1

Time: O(n log n) — dominated by sorting the copy.
Space: O(n) — the sorted copy holds all n elements.

Approach 2 — One-Pass Linear Scan

Scan left to right tracking the running maximum: any element strictly less than the running maximum is out of place, so the right boundary is the last such element. Then scan right to left tracking the running minimum: any element strictly greater than the running minimum is out of place, giving the left boundary.

1. Initialize right_boundary = -1 and running_max = -∞.
2. Scan left to right: if nums[i] < running_max, update right_boundary = i; otherwise update running_max = nums[i].
3. Initialize left_boundary = -1 and running_min = +∞.
4. Scan right to left: if nums[i] > running_min, update left_boundary = i; otherwise update running_min = nums[i].
5. If right_boundary == -1, return 0; otherwise return right_boundary - left_boundary + 1.

1class Solution:
2    def findUnsortedSubarray(self, nums: List[int]) -> int:
3        n = len(nums)
4        left_boundary = -1
5        right_boundary = -1
6        running_max = float('-inf')
7        running_min = float('inf')
8
9        for i in range(n):
10            if nums[i] < running_max:
11                right_boundary = i  # out of place from the left; push dirty region rightward
12            else:
13                running_max = nums[i]
14
15        for i in range(n - 1, -1, -1):
16            if nums[i] > running_min:
17                left_boundary = i  # out of place from the right; push dirty region leftward
18            else:
19                running_min = nums[i]
20
21        if right_boundary == -1:
22            return 0  # running_max never exceeded any element; array is already sorted
23
24        return right_boundary - left_boundary + 1

Time: O(n) — two linear passes, no sorting.
Space: O(1) — only a handful of scalar variables regardless of input size.

Complexity Summary

Common Mistakes

• Using ≤ instead of < in the forward scan: only elements strictly less than the running maximum are out of place. Changing to ≤ would incorrectly treat equal adjacent elements as disordered, inflating the answer.
• Forgetting the already-sorted check: if right_boundary remains -1 and you return right_boundary - left_boundary + 1 anyway, you get -1 - (-1) + 1 = 1, which is wrong. The guard on right_boundary == -1 is essential.
• Scanning right to left with the wrong comparison: the backward pass catches elements greater than the running minimum (meaning their left neighbor should be ≤ them but isn't). Swapping to < produces an incorrect left boundary.
• Initializing left_boundary to 0 instead of -1: if the leftmost element is already in its correct position, starting at 0 overstates the answer by 1.
• In sort-and-compare, starting the right boundary scan from left_boundary instead of the end: the right boundary must scan from the far end of the array to find the last mismatch, not the first one after the left boundary.

Related Problems

• Sort Colors — partitions an array into sorted regions in-place, requiring the same boundary-detection thinking about where elements belong
• Move Zeroes — in-place rearrangement that identifies a "clean" ordered region versus a region that needs fixing, same general flavor
• Next Permutation — scans right-to-left to find the first element that breaks descending order, the same backward disorder-detection technique used here
• Merge Intervals — works with overlapping spans in a sorted array, analogous to finding and collapsing a "dirty" region
• Subarray Sum Equals K — another subarray boundary problem solved by clever linear scanning rather than brute-force enumeration