🌱 Keegan's Digital Garden

581. Shortest Unsorted Continuous Subarray

3 min read

📝 Problem Details

input array nums find one continuous subarray such that if you only sort this subarray in increasing order then the whole array will be sorted return the shortest subarray and output its length

💭What Were My Initial Thoughts?

brute force:
- make a copy of the input array and sort it 
- compare the sorted array with the original array by its min and max value positions

- can probably do this inplace without the sorting using a two pointers approach

💡 Explanation of Solution

The key idea is to identify the boundaries of the subarray that needs sorting:

1. Traverse from the left and stop when you find the first element that breaks the increasing order — this is the initial left boundary.

2. Traverse from the right and stop when you find the first element that breaks the decreasing order — this is the initial right boundary.

3. The subarray between these two points is unsorted, but we need to double-check if elements just outside these boundaries also break the sorted condition once the subarray is sorted.

4. Find the minimum and maximum values within the initially identified unsorted subarray.

5. Expand the left boundary to include any values greater than the minimum of the unsorted subarray, as they would be out of place.

6. Similarly, expand the right boundary to include any values less than the maximum of the unsorted subarray.

7. The final answer is the length of this extended subarray.

This avoids sorting the entire array and solves the problem in linear time.

⌛ Complexity Analysis

- Time Complexity: O(n)
  - We traverse the array at most four times: once to find left boundary, once to find right boundary, once to find min and max, and once each to expand the boundaries.

- Space Complexity: O(1)
  - We use only a constant amount of extra space regardless of input size.

💻 Implementation of Solution

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        /*
            approach:
            - two pointers
            - find the left and right boundaries where the array is unsorted
            - the minimum element in the unsorted region 
            - the maximum element in the unsorted region
        */
    
        int n = nums.size();
        int left = 0;
        int right = n - 1;
 
        // step 1: find initial left boundary
        while(left < n -1 && nums[left] <= nums[left+1]) left++;
 
        // early exit in case of array already being sorted
        if(left == n-1 ) return 0;
 
        // step 2: find initial right boundary 
        while(right > 0 && nums[right] >= nums[right-1]) right--;
 
        // step 3: find min and max in the unsorted subarray
        int subMin = INT_MAX;
        int subMax = INT_MIN;
        for(int i = left; i <= right; i++) {
            subMin = min(subMin, nums[i]);
            subMax = max(subMax, nums[i]);
        }
 
        // step 4: expand left boundary
        while(left > 0 && nums[left - 1] > subMin) left--;
        // step 5: expand right boundary
        while(right < n-1 && nums[right + 1] < subMax) right++;
 
        return right - left + 1;
    }
};

Graph View