We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Shortest Unsorted Continuous Subarray

Difficulty: Medium

Problem Description

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 length of the shortest such subarray.

Key Insights

  • Identify the first and last indices where the order of the array is violated.
  • Elements outside this range need to be considered for sorting to ensure the entire array becomes sorted.
  • Use a two-pointer approach to find the boundaries of the unsorted subarray.
  • The solution should be efficient, ideally O(n) time complexity.

Space and Time Complexity

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

Solution

To solve this problem, we can use a two-pointer technique along with a stack. We will find the first and last indices where the array is not sorted. By tracking the minimum and maximum values within that unsorted range, we can determine if any elements outside this range need to be included in the sorting process.

  1. Traverse the array from the beginning to find the first index where the order is violated.
  2. Traverse the array from the end to find the last index where the order is violated.
  3. Determine the minimum and maximum values in the identified subarray.
  4. Expand the boundaries if there are elements outside the identified range that are greater than the minimum or less than the maximum of the identified subarray.

This approach ensures we can find the length of the shortest unsorted continuous subarray efficiently.

Code Solutions

def findUnsortedSubarray(nums):
    n = len(nums)
    left, right = 0, n - 1
    
    # Find the first out of order from the left
    while left < n - 1 and nums[left] <= nums[left + 1]:
        left += 1
    
    # If the whole array is sorted
    if left == n - 1:
        return 0
    
    # Find the first out of order from the right
    while right > 0 and nums[right] >= nums[right - 1]:
        right -= 1
    
    # Determine min and max in the unsorted subarray
    subarray_min = min(nums[left:right + 1])
    subarray_max = max(nums[left:right + 1])
    
    # Expand the left boundary
    while left > 0 and nums[left - 1] > subarray_min:
        left -= 1
    
    # Expand the right boundary
    while right < n - 1 and nums[right + 1] < subarray_max:
        right += 1
    
    return right - left + 1
← Back to All Questions