LeetCode 581: Shortest Unsorted Continuous Subarray

Problem Restatement

We are given an integer array nums.

We need to find the shortest continuous subarray such that, if we sort only that subarray in non-decreasing order, the whole array becomes sorted in non-decreasing order.

Return the length of that subarray.

If the array is already sorted, return 0. The constraints are 1 <= nums.length <= 10^4 and -10^5 <= nums[i] <= 10^5. The follow-up asks for an O(n) solution.

Input and Output

Example function shape:

def findUnsortedSubarray(nums: list[int]) -> int:
    ...

Examples

Example 1:

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

Output:

5

The subarray is:

[6, 4, 8, 10, 9]

If we sort only this part, the array becomes:

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

So the answer is 5.

Example 2:

nums = [1, 2, 3, 4]

Output:

0

The array is already sorted.

Example 3:

nums = [1]

Output:

0

A single-element array is already sorted.

First Thought: Sort and Compare

A simple solution is to compare the array with its sorted version.

nums        = [2, 6, 4, 8, 10, 9, 15]
sorted_nums = [2, 4, 6, 8, 9, 10, 15]

The first index where they differ is 1.

The last index where they differ is 5.

So the shortest subarray length is:

5 - 1 + 1 = 5

This approach is easy and correct, but it costs O(n log n) time because of sorting.

The follow-up asks for O(n), so we can do better.

Key Insight

We need to find the left and right boundaries of the unsorted region.

The right boundary is the last index where the current value is smaller than something before it.

Scan from left to right while tracking the maximum value seen so far.

If:

nums[i] < max_seen

then nums[i] is too small to stay at index i. It must be inside the unsorted subarray. So we update the right boundary.

The left boundary is symmetric.

Scan from right to left while tracking the minimum value seen so far.

If:

nums[i] > min_seen

then nums[i] is too large to stay at index i. It must be inside the unsorted subarray. So we update the left boundary.

Algorithm

1. Set right = -1.
2. Scan from left to right.
3. Track max_seen, the largest value seen so far.
4. If nums[i] < max_seen, update right = i.

Then:

1. Set left = 0.
2. Scan from right to left.
3. Track min_seen, the smallest value seen so far.
4. If nums[i] > min_seen, update left = i.

Finally:

1. If right == -1, the array is already sorted.
2. Otherwise, return right - left + 1.

Correctness

During the left-to-right scan, max_seen is the largest value among all elements from index 0 to index i.

If nums[i] < max_seen, then some earlier value is greater than nums[i]. Therefore, the array cannot be sorted unless index i is included in the subarray to be sorted. Updating right = i ensures that the right boundary reaches every such out-of-order position.

If nums[i] >= max_seen, then nums[i] is at least as large as every value before it, so this scan gives no reason to include index i as a right-side violation.

During the right-to-left scan, min_seen is the smallest value among all elements from index i to the end.

If nums[i] > min_seen, then some later value is smaller than nums[i]. Therefore, the array cannot be sorted unless index i is included in the subarray to be sorted. Updating left = i ensures that the left boundary reaches every such out-of-order position.

After both scans, every index outside [left, right] is already compatible with the sorted order of all elements around it. Every index that must move because of a larger earlier value or smaller later value is included. Therefore, sorting exactly nums[left:right + 1] is sufficient and minimal.

If no right-side violation is found, then no element is smaller than a previous maximum. That means the entire array is already non-decreasing, so the correct answer is 0.

Complexity

Implementation

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

        max_seen = nums[0]
        right = -1

        for i in range(n):
            if nums[i] < max_seen:
                right = i
            else:
                max_seen = nums[i]

        min_seen = nums[-1]
        left = 0

        for i in range(n - 1, -1, -1):
            if nums[i] > min_seen:
                left = i
            else:
                min_seen = nums[i]

        if right == -1:
            return 0

        return right - left + 1

Code Explanation

This variable stores the largest value seen while scanning from left to right:

max_seen = nums[0]

The right boundary starts at -1:

right = -1

If the array is already sorted, right will never change.

During the left-to-right scan:

if nums[i] < max_seen:
    right = i
else:
    max_seen = nums[i]

If the current number is smaller than a previous number, it is out of order. So it must be inside the subarray.

Then we scan from right to left:

min_seen = nums[-1]
left = 0

During this scan:

if nums[i] > min_seen:
    left = i
else:
    min_seen = nums[i]

If the current number is larger than a later number, it is out of order. So it must be inside the subarray.

Finally:

if right == -1:
    return 0

No violation means the array is already sorted.

Otherwise:

return right - left + 1

This returns the length of the shortest subarray.

Testing

def run_tests():
    s = Solution()

    assert s.findUnsortedSubarray([2, 6, 4, 8, 10, 9, 15]) == 5
    assert s.findUnsortedSubarray([1, 2, 3, 4]) == 0
    assert s.findUnsortedSubarray([1]) == 0
    assert s.findUnsortedSubarray([1, 3, 2, 2, 2]) == 4
    assert s.findUnsortedSubarray([2, 1]) == 2
    assert s.findUnsortedSubarray([1, 2, 4, 5, 3]) == 3

    print("all tests passed")

run_tests()

Test meaning: