Shorted Unsorted Subarray

Given an integer array nums, we have to find one subarray (contiguous elements of an array) that if we sort only this array in ascending order, the whole will be sorted in ascending order.

Return the start and end indices of shortest such array. If the array is already sorted, return [-1, -1].

Example 1

• Input: nums = [1,2,6,4,7,8,10,9,12]
• Output: [2,7]
• Explanation: If we sort the subarray [6,4,7,8,10,9], the whole array will get sorted.

Example 2

• Input: nums = [4,6,8,10]
• Output: [-1, -1]
• Explanation: The array is already sorted in ascending order.

Approach 1: Sorting

Idea

If we sort the given array and check in which indices (from both start and end) where the elements start mismatching with original array, we can say if we sort the subarray form by those indices, the whole array will get sorted.

Implementation

We will create new sorted array and find the left most and right nost indices simply by comparing the elements.

vector<int> findUnsortedSubarray(vector<int>& nums) {
    vector<int> sortedArray = nums;
    sort(sortedArray.begin(), sortedArray.end());
    int start = -1, end = -1;
    for (int i = 0; i < (int)nums.size(); ++i) {
        if (nums[i] != sortedArray[i]) {
            start = i;
            break;
        }
    }
    for (int i = (int)nums.size() - 1; i >= 0; --i) {
        if (nums[i] != sortedArray[i]) {
            end = i;
            break;
        }
    }
    return {start, end};

Complexity Analysis

• Time Complexity: $O(NlogN)$ for sorting (where $N=$ the length of the array)
• Space Complexity: $O(N)$ since we are copying the array (for sorting, assuming quick sort is used the space complexity is $O(logN)$).

Approach 2: Traversing from Both End

Idea

In the above solution, we are sorting the array even if the only small part of the array is unsorted. So, we can try finding the first out-of-order element without sorting.

• Finding the first out-of-order elements

  • We will scan the array from left to right array and find the element which is smaller than the previous element. Let’s say this index is $S$.
  • Then, we will perform similar steps but from right to left. If an element is greater than the next element, we will keep track of this index. Let’s say this index is $E$.

• Check whether sorting the subarray formed by those out-of-order elements sort the array

  • Find the minimum and maximum elements formed by $S$ and $E$ (nums[S…E]). Let’s denote them by currentMinima and currentMaxima.
  • If there is any element in the first part of the array (nums[0…S]) which is greater the currentMinima, update $S$ with this index.
  • Similarly, if there is any element in the last part of the array(nums[E + 1…N]), which is smaller than the currentMaxima, update $E$ with this index.

Implementation

vector<int> findUnsortedSubarray(vector<int>& nums) {
    int startSubarrayIdx = -1, endSubarrayIdx = -1;
    int n = nums.size();
    for (int i = 0; i < n - 1; ++i) {
        if (nums[i] > nums[i + 1]) {
            startSubarrayIdx = i;
            break;
        }
    }
    if (startSubarrayIdx == -1) {
        return {-1, -1};
    }
    for (int i = n - 1; i >= 1; --i) {
        if (nums[i] < nums[i - 1]) {
            endSubarrayIdx = i;
            break;
        }
    }
    int currentMaxima = INT_MIN, currentMinima = INT_MAX;
    for (int i = startSubarrayIdx; i <= endSubarrayIdx; ++i) {
        currentMaxima = max(currentMaxima, nums[i]);
        currentMinima = min(currentMinima, nums[i]);
    }
    for (int i = 0; i < startSubarrayIdx; ++i) {
        if (nums[i] > currentMinima) {
            startSubarrayIdx = i;
            break;
        }
    }
    for (int i = n - 1; i >= endSubarrayIdx + 1; --i) {
        if (nums[i] < currentMaxima) {
            endSubarrayIdx = i;
            break;
        }
    }
    return {startSubarrayIdx, endSubarrayIdx};
}

Complexity Analysis

• Time Complexity: $O(N)$, we are traversing the array twice at the worst case
• Space Complexity: $O(1)$, only constant extra space is used

Approach 3: Traversing from Both End - Simpler

Idea

We can simplify the above approach by keeping track of the maximum found element (from left) and minimum found element (from right).

• When traversing from left to right, if we find an element that is greater than the current maxima, we will update the current maxima with this value. If the current element is greater than the current maxima, we will keep track of the index. This simply means the current element does not follow the ascending order rule as thus out-of-order. Say this index is $E$.
• When traversing from right to left, if we find an element that is lesser than the current minima, we will update the current minima with this value. If the current element is lesser than the current minima, we will keep track of the index. Again, this element does not follow the ascending order rule. Say this index is $S$.

Once the traversal is complete, the answer will be $[S, E]$.

Implementation

vector<int> findUnsortedSubarray(vector<int>& nums) {
    int startSubarrayIdx = -1, endSubarrayIdx = -1;
    int currentMaxima = INT_MIN, currentMinima = INT_MAX;
    for (int i = 0; i < (int)nums.size(); ++i) {
        currentMaxima = max(currentMaxima, nums[i]);
        if (currentMaxima > nums[i]) {
            // this element is out of order
            endSubarrayIdx = i;
        }
    }
    if (endSubarrayIdx == -1) {
        return {-1, -1};
    }
    for (int i = (int)nums.size() - 1; i >= 0; --i) {
        currentMinima = min(currentMinima, nums[i]);
        if (currentMinima < nums[i]) {
            // this element is out of order
            startSubarrayIdx = i;
        }
    }
    return {startSubarrayIdx, endSubarrayIdx};
}

Complexity Analysis

• Time Complexity: $O(N)$, we are traversing the array twice
• Space Complexity: $O(1)$, only constant extra space is used