algoadvance

Leetcode 581. Shortest Unsorted Continuous Subarray

Problem Statement

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

Example:

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

Clarifying Questions:

  1. What should be returned if the array is empty?
    • The length should be 0 as there’s nothing to sort.
  2. Are there any constraints on the values of the elements in the array or its length?
    • The problem didn’t specify constraints, but typically, for problems of this nature, constraints like 1 <= nums.length <= 10^4 and -10^5 <= nums[i] <= 10^5 can be assumed.
  3. What is the expected time complexity?
    • The optimal solution would ideally have a time complexity of O(n) where n is the length of the array.

Strategy:

  1. Identify the Unsorted Subarray:
    • Traverse from the beginning of the array to find the first element which is greater than the next element (left boundary of subarray).
    • Traverse from the end of the array to find the first element which is less than the previous element (right boundary of subarray).
  2. Determine the Required Sorting Range:
    • The subarray between the identified boundaries may need further adjustment if there are elements in this range that are out of the final sorted order’s range.
    • Find the maximum and minimum values in this subarray.
    • Extend the boundaries if necessary to include all elements that are out of order concerning the found minimum and maximum.
  3. Calculate the Length of the Subarray:
    • If the array is already sorted, return 0. Otherwise, return the length between the identified boundaries.

Code Implementation:

#include <vector>
#include <algorithm>
#include <limits.h>

class Solution {
public:
    int findUnsortedSubarray(std::vector<int>& nums) {
        int n = nums.size();
        int start = -1, end = -1;
        
        // Traverse from beginning to find the first out of order element.
        for (int i = 1; i < n; ++i) {
            if (nums[i] < nums[i - 1]) {
                start = i - 1;
                break;
            }
        }
        
        // Traverse from end to find the first out of order element.
        for (int i = n - 1; i > 0; --i) {
            if (nums[i] < nums[i - 1]) {
                end = i;
                break;
            }
        }
        
        // If already sorted
        if (start == -1 && end == -1) return 0;
        
        // Find min and max in the unsorted subarray
        int subarray_min = INT_MAX, subarray_max = INT_MIN;
        for (int i = start; i <= end; ++i) {
            if (nums[i] < subarray_min) subarray_min = nums[i];
            if (nums[i] > subarray_max) subarray_max = nums[i];
        }
        
        // Extend the start to the left
        while (start > 0 && nums[start - 1] > subarray_min) --start;
        // Extend the end to the right
        while (end < n - 1 && nums[end + 1] < subarray_max) ++end;
        
        return end - start + 1;
    }
};

Time Complexity:

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI