581. Shortest Unsorted Continuous Subarray

Problem Description

Given an integer array nums, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending 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

Constraints:

• 1 <= nums.length <= 10⁴
• -10⁵ <= nums[i] <= 10⁵

Python Solution

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 2:
            return 0
        
        # Find the first number out of order from left
        left = 0
        while left < n - 1 and nums[left] <= nums[left + 1]:
            left += 1
        
        if left == n - 1:  # Array is already sorted
            return 0
        
        # Find the first number out of order from right
        right = n - 1
        while right > 0 and nums[right] >= nums[right - 1]:
            right -= 1
        
        # Find min and max in the middle subarray
        min_val = min(nums[left:right + 1])
        max_val = max(nums[left:right + 1])
        
        # Extend left boundary
        while left > 0 and nums[left - 1] > min_val:
            left -= 1
        
        # Extend right boundary
        while right < n - 1 and nums[right + 1] < max_val:
            right += 1
        
        return right - left + 1

Java Solution

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return 0;
        }
        
        // Find the first number out of order from left
        int left = 0;
        while (left < n - 1 && nums[left] <= nums[left + 1]) {
            left++;
        }
        
        if (left == n - 1) {  // Array is already sorted
            return 0;
        }
        
        // Find the first number out of order from right
        int right = n - 1;
        while (right > 0 && nums[right] >= nums[right - 1]) {
            right--;
        }
        
        // Find min and max in the middle subarray
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int i = left; i <= right; i++) {
            min = Math.min(min, nums[i]);
            max = Math.max(max, nums[i]);
        }
        
        // Extend left boundary
        while (left > 0 && nums[left - 1] > min) {
            left--;
        }
        
        // Extend right boundary
        while (right < n - 1 && nums[right + 1] < max) {
            right++;
        }
        
        return right - left + 1;
    }
}

C++ Solution

class Solution {
public:
    int findUnsortedSubarray(vector& nums) {
        int n = nums.size();
        if (n < 2) {
            return 0;
        }
        
        // Find the first number out of order from left
        int left = 0;
        while (left < n - 1 && nums[left] <= nums[left + 1]) {
            left++;
        }
        
        if (left == n - 1) {  // Array is already sorted
            return 0;
        }
        
        // Find the first number out of order from right
        int right = n - 1;
        while (right > 0 && nums[right] >= nums[right - 1]) {
            right--;
        }
        
        // Find min and max in the middle subarray
        int min_val = INT_MAX;
        int max_val = INT_MIN;
        for (int i = left; i <= right; i++) {
            min_val = min(min_val, nums[i]);
            max_val = max(max_val, nums[i]);
        }
        
        // Extend left boundary
        while (left > 0 && nums[left - 1] > min_val) {
            left--;
        }
        
        // Extend right boundary
        while (right < n - 1 && nums[right + 1] < max_val) {
            right++;
        }
        
        return right - left + 1;
    }
};

JavaScript Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
var findUnsortedSubarray = function(nums) {
    const n = nums.length;
    if (n < 2) {
        return 0;
    }
    
    // Find the first number out of order from left
    let left = 0;
    while (left < n - 1 && nums[left] <= nums[left + 1]) {
        left++;
    }
    
    if (left === n - 1) {  // Array is already sorted
        return 0;
    }
    
    // Find the first number out of order from right
    let right = n - 1;
    while (right > 0 && nums[right] >= nums[right - 1]) {
        right--;
    }
    
    // Find min and max in the middle subarray
    let min = Math.min(...nums.slice(left, right + 1));
    let max = Math.max(...nums.slice(left, right + 1));
    
    // Extend left boundary
    while (left > 0 && nums[left - 1] > min) {
        left--;
    }
    
    // Extend right boundary
    while (right < n - 1 && nums[right + 1] < max) {
        right++;
    }
    
    return right - left + 1;
};

C# Solution

public class Solution {
    public int FindUnsortedSubarray(int[] nums) {
        int n = nums.Length;
        if (n < 2) {
            return 0;
        }
        
        // Find the first number out of order from left
        int left = 0;
        while (left < n - 1 && nums[left] <= nums[left + 1]) {
            left++;
        }
        
        if (left == n - 1) {  // Array is already sorted
            return 0;
        }
        
        // Find the first number out of order from right
        int right = n - 1;
        while (right > 0 && nums[right] >= nums[right - 1]) {
            right--;
        }
        
        // Find min and max in the middle subarray
        int min = int.MaxValue;
        int max = int.MinValue;
        for (int i = left; i <= right; i++) {
            min = Math.Min(min, nums[i]);
            max = Math.Max(max, nums[i]);
        }
        
        // Extend left boundary
        while (left > 0 && nums[left - 1] > min) {
            left--;
        }
        
        // Extend right boundary
        while (right < n - 1 && nums[right + 1] < max) {
            right++;
        }
        
        return right - left + 1;
    }
}