Shortest Unsorted Continuous Subarray

The Problem:

Given an integer array nums, you need to find one continuous subarray such that if you only sort this subarray in non-decreasing order, then the whole array will be sorted in non-decreasing order.

Return the shortest such subarray and output its length.

Example 1:

Input: nums = [2,6,4,8,10,9,15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

Example 2:

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

Example 3:

Input: nums = [1]
Output: 0

Let me walk you through how I approached this problem and refined my solution!

Step 1: Initial Observations

First, I noticed that:

1. If the array is already sorted → return 0.
2. The unsorted portion must be continuous.
3. The solution requires finding start and end indices of this subarray.

But how? 🤔

Step 2: First Attempt - Find Where Order Breaks

I thought:

1. Traverse from the left until the ascending order breaks (nums[i] > nums[i+1]).
2. Traverse from the right until the descending order breaks (nums[j] < nums[j-1]).

Example:

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

1. Left stops at 6 > 4 (index 1)
2. Right stops at 9 < 10 (index 5)
3. Subarray length = 5 - 1 + 1 = 5 ✅

But this fails for cases like [1,3,5,4,2,6,7]!

Step 3: The Hidden Problem

In [1,3,5,4,2,6,7]:

Initial boundaries: [5, 4, 2] (indices 2 to 4)

But sorting just this gives [1,3,2,4,5,6,7] → still unsorted!

Why?

• The 3 before the subarray is greater than the min (2) in the subarray.
• So, we must expand the left boundary to include 3.

Step 4: Fixing the Approach

New Insight:

1. After finding initial left and right, compute min and max in the subarray.
2. Expand left if any element before left is > min.
3. Expand right if any element after right is < max.

Example:

[1,3,5,4,2,6,7]

1. Initial subarray: [5,4,2] (min=2, max=5)
2. nums[1] = 3 > min=2 → expand left to 1
3. Final subarray: [3,5,4,2] → now sorting it works!

Step 5: Final Algorithm

1. Find left: Traverse until nums[i +1 ] < nums[i].
2. Find right: Traverse backward until nums[j] < nums[j-1].
3. Get min/max in subarray [left, right].
4. Expand left if nums[left-1] > min.
5. Expand right if nums[right+1] < max.
6. Return right - left + 1.

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

FUNCTION findUnsortedSubarray(nums):
  IF length(nums) < 2:
    RETURN 0
   
  // Find initial left boundary
  left = 0
  WHILE left < length(nums)-1 AND nums[left] <= nums[left+1]:
    left++
   
  // If entire array is sorted
  IF left == length(nums)-1:
    RETURN 0
   
  // Find initial right boundary
  right = length(nums)-1
  WHILE right > 0 AND nums[right] >= nums[right-1]:
    right--
   
  // Find min and max in unsorted subarray
  min_val = MIN(nums[left..right])
  max_val = MAX(nums[left..right])
   
  // Expand left boundary
  WHILE left > 0 AND nums[left-1] > min_val:
    left--
   
  // Expand right boundary
  WHILE right < length(nums)-1 AND nums[right+1] < max_val:
    right++
   
  RETURN right - left + 1

The actual code:

function findUnsortedSubarray(nums) {
    let left = 0, right = nums.length - 1; 

// Find left boundary
while (left < nums.length - 1 && nums[left] <= nums[left + 1]){
 left++;
} 

if (left === nums.length - 1) return 0; // Already sorted

 // Find right boundary
while ( 0 < right &&  nums[right - 1] <= nums[right]) right--;

// Expand left
while (left > 0 && nums[left - 1] > min) left--;
    

// Expand right
while (right < nums.length - 1 && nums[right + 1] < max) {
right++;
}
    
return right - left + 1;
}

Key Takeaways

1. Initial boundaries may not be enough → need to check beyond them.
2. Min/max in subarray helps identify "hidden" unsorted elements.
3. Edge cases matter (already sorted, equal values).

This problem teaches us to look beyond the obvious when dealing with subarrays!