Code Implementation

class Solution:
    def findUnsortedSubarray(self, nums):
        n = len(nums)
        start, end = -1, -2  # ensures 0 if already sorted
        min_num, max_num = nums[-1], nums[0]
        for i in range(1, n):
            max_num = max(max_num, nums[i])
            min_num = min(min_num, nums[n - 1 - i])
            if nums[i] < max_num:
                end = i
            if nums[n - 1 - i] > min_num:
                start = n - 1 - i
        return end - start + 1
    

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int n = nums.size();
        int start = -1, end = -2;
        int min_num = nums[n - 1], max_num = nums[0];
        for (int i = 1; i < n; ++i) {
            max_num = max(max_num, nums[i]);
            min_num = min(min_num, nums[n - 1 - i]);
            if (nums[i] < max_num) end = i;
            if (nums[n - 1 - i] > min_num) start = n - 1 - i;
        }
        return end - start + 1;
    }
};
    

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        int start = -1, end = -2;
        int min = nums[n - 1], max = nums[0];
        for (int i = 1; i < n; i++) {
            max = Math.max(max, nums[i]);
            min = Math.min(min, nums[n - 1 - i]);
            if (nums[i] < max) end = i;
            if (nums[n - 1 - i] > min) start = n - 1 - i;
        }
        return end - start + 1;
    }
}
    

var findUnsortedSubarray = function(nums) {
    let n = nums.length;
    let start = -1, end = -2;
    let min = nums[n - 1], max = nums[0];
    for (let i = 1; i < n; i++) {
        max = Math.max(max, nums[i]);
        min = Math.min(min, nums[n - 1 - i]);
        if (nums[i] < max) end = i;
        if (nums[n - 1 - i] > min) start = n - 1 - i;
    }
    return end - start + 1;
};
    

Problem Description

Given an integer array nums, you are to find the shortest continuous subarray (contiguous sequence of elements) that, if you sorted only this subarray in-place, the entire array would become sorted in ascending order.

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

Constraints:

• There is exactly one valid answer for each input.
• Elements may repeat, but you must not "reuse" or skip elements — the subarray must be a single, continuous block.
• All input is a single array nums of integers.

Thought Process

At first glance, you might consider comparing the array to its sorted version to find the first and last places they differ. This would work, but sorting takes O(n log n) time and extra space.

To improve, think about what it means for a subarray to be "out of order": somewhere, elements are smaller or larger than they should be. If you could find the leftmost and rightmost positions where the order is violated, you could identify the minimal unsorted subarray.

Instead of sorting, can we scan from both ends and track the largest and smallest values seen so far? If an element is smaller than a previous max (from the left), it's out of order; if larger than a later min (from the right), it's also out of order. This leads to an efficient O(n) solution.

Solution Approach

Here’s how the optimized algorithm works step by step:

1. Initialize Variables:
   • Let start and end mark the bounds of the unsorted subarray. Initialize them so that if the array is already sorted, the result is zero.
   • Track max_num (maximum seen from the left) and min_num (minimum seen from the right).
2. Left-to-Right Pass:
   • Iterate from the start of the array.
   • Update max_num to the maximum so far.
   • If the current number is less than max_num, it's out of order; update end to the current index.
3. Right-to-Left Pass:
   • Iterate from the end of the array backwards.
   • Update min_num to the minimum so far.
   • If the current number is greater than min_num, it's out of order; update start to the current index.
4. Result:
   • The length of the subarray is end - start + 1.
   • If the array was already sorted, end < start and the result is zero.

This approach uses only O(1) extra space and O(n) time.

Example Walkthrough

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

1. Left-to-Right:
   • max_num starts at 2.
   • At index 1: max_num=6; nums[1]=6 (OK)
   • At index 2: max_num=6; nums[2]=4 < 6 ⇒ out of order, end=2
   • At index 3: max_num=8; nums[3]=8 (OK)
   • At index 4: max_num=10; nums[4]=10 (OK)
   • At index 5: max_num=10; nums[5]=9 < 10 ⇒ out of order, end=5
   • At index 6: max_num=15; nums[6]=15 (OK)
2. Right-to-Left:
   • min_num starts at 15.
   • At index 5: min_num=9; nums[5]=9 (OK)
   • At index 4: min_num=9; nums[4]=10 > 9 ⇒ out of order, start=4
   • At index 3: min_num=8; nums[3]=8 (OK)
   • At index 2: min_num=4; nums[2]=4 (OK)
   • At index 1: min_num=4; nums[1]=6 > 4 ⇒ out of order, start=1
   • At index 0: min_num=2; nums[0]=2 (OK)
3. Result:
   • start=1, end=5 ⇒ length = 5
   • So, sorting nums[1:6] (i.e., [6,4,8,10,9]) will sort the whole array.

Time and Space Complexity

• Brute-force approach:
  • Sort the array and compare: O(n log n) time, O(n) space (for the copy).
• Optimized approach (described above):
  • O(n) time: One pass from each end.
  • O(1) space: Only a few extra variables, no extra arrays.

The optimized solution is much more efficient, especially for large arrays.

Summary

The key insight is that you don't need to sort or use extra space to find the shortest unsorted subarray. By scanning from both ends and tracking the running maximum and minimum, you can efficiently pinpoint the exact range that needs sorting. This elegant O(n) solution leverages the properties of arrays and sorting, making it both fast and space-efficient.