Shortest Unsorted Continuous Subarray [Medium] — Linear Scan

Problem Statement

Find the one contiguous subarray, which if you only sort this subarray in place, results in the whole array being sorted. Return its length.

Input: [2,6,4,8,10,9,15] → Output: 5 (sort [6,4,8,10,9])

Intuition

Scan left→right: any element smaller than the running max must be included (track rightmost such). Scan right→left: any element larger than running min must be included (track leftmost such).

Solutions

C++

int findUnsortedSubarray(vector<int>& nums) {
    int n=nums.size(), left=-1, right=-2, mn=nums[n-1], mx=nums[0];
    for(int i=1;i<n;i++){mx=max(mx,nums[i]);if(nums[i]<mx)right=i;}
    for(int i=n-2;i>=0;i--){mn=min(mn,nums[i]);if(nums[i]>mn)left=i;}
    return right-left+1;
}

Python

def findUnsortedSubarray(nums: list[int]) -> int:
    n = len(nums)
    left, right = -1, -2
    max_val, min_val = nums[0], nums[-1]
    for i in range(1, n):
        max_val = max(max_val, nums[i])
        if nums[i] < max_val:
            right = i
    for i in range(n-2, -1, -1):
        min_val = min(min_val, nums[i])
        if nums[i] > min_val:
            left = i
    return right - left + 1

Complexity

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