Problem statement

Given an integer array nums, find the shortest contiguous subarray such that sorting that subarray in ascending order leaves the whole array sorted in ascending order.

Return the length of that subarray. If the array is already sorted, return 0.

Example 1

Input: nums = [2,6,4,8,10,9,15]
Output: 5
Explanation: Sorting [6,4,8,10,9] sorts the whole array.

Example 2

Input: nums = [1,2,3,4]
Output: 0

Example 3

Input: nums = [1]
Output: 0

Constraints

• 1 <= nums.length <= 40
• -1000 <= nums[i] <= 1000

Follow-up: Can you do it in O(n) without sorting?

Hints for Shortest Unsorted Continuous Subarray

1. Hint 1

   Compare the array with its sorted copy: the answer spans the first and last positions that differ.

2. Hint 2

   For O(n), sweep right tracking the running maximum — the last index that falls below it is the right edge.

3. Hint 3

   Sweep left tracking the running minimum to find the left edge the same way.

How to solve Shortest Unsorted Continuous Subarray

Compare the array with its sorted copy: everything outside the first and last mismatches is already in its final place.

Approach

1. Sort a copy.
2. Advance left while nums[left] == sorted[left].
3. Retreat right while nums[right] == sorted[right].
4. Return 0 if left ran off the end, else right - left + 1.

Why it works

Positions where the original already matches its sorted counterpart need not move, and the window between the outermost mismatches is the minimal region whose sort fixes the array.

Complexity

• Time — O(n log n)
• Space — O(n)

Pitfalls

• The O(n) version sweeps right tracking the running max (the last index below it is the right edge) and left tracking the running min for the left edge.
• An already-sorted array must return 0, not 1.

Reference solution

Python

def findUnsortedSubarray(nums):
    sorted_nums = sorted(nums)
    left, right = 0, len(nums) - 1
    while left < len(nums) and nums[left] == sorted_nums[left]:
        left += 1
    while right > left and nums[right] == sorted_nums[right]:
        right -= 1
    return 0 if left >= len(nums) else right - left + 1

Java

public static int findUnsortedSubarray(int[] nums) {
    int[] sorted = Arrays.copyOf(nums, nums.length);
    Arrays.sort(sorted);
    int left = 0, right = nums.length - 1;
    while (left < nums.length && nums[left] == sorted[left]) left++;
    while (right > left && nums[right] == sorted[right]) right--;
    return left >= nums.length ? 0 : right - left + 1;
}

C++

int findUnsortedSubarray(vector<int>& nums) {
    vector<int> sorted = nums;
    sort(sorted.begin(), sorted.end());
    int n = (int) nums.size();
    int left = 0, right = n - 1;
    while (left < n && nums[left] == sorted[left]) left++;
    while (right > left && nums[right] == sorted[right]) right--;
    return left >= n ? 0 : right - left + 1;
}

JavaScript

var findUnsortedSubarray = function(nums) {
    const sorted = nums.slice().sort(function(a, b) { return a - b; });
    let left = 0, right = nums.length - 1;
    while (left < nums.length && nums[left] === sorted[left]) left++;
    while (right > left && nums[right] === sorted[right]) right--;
    return left >= nums.length ? 0 : right - left + 1;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium