Shortest Unsorted Continuous Subarray - Leetcode Solution

The 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 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 Explanation: The whole array is already sorted in ascending order.

Approach:

One of the simplest approaches to solve this problem is to first copy the given array and sort it in ascending order. After sorting, we can compare both the original and the sorted arrays element by element from the start and the end of the arrays.

The first element in the original array that is not equal to the same element in the sorted array would be the starting index of our unsorted subarray. Similarly, the last element in the original array that is not equal to the same element in the sorted array would be the ending index of our unsorted subarray.

The length of the subarray would be the difference between the ending and the starting indices plus one.

Solution:

class Solution { public: int findUnsortedSubarray(vector<int>& nums) { vector<int> sorted_arr(nums); sort(sorted_arr.begin(), sorted_arr.end());

    int start_index = nums.size();
    int end_index = 0;
    
    for(int i=0;i<nums.size();i++){
        if(nums[i]!=sorted_arr[i]){
            start_index = min(start_index, i);
            end_index = max(end_index, i);
        }
    }
    
    if(end_index-start_index<=0){
        return 0;
    }
    return end_index-start_index+1;
}

};

In this solution, we first create a new vector sorted_arr which is a copy of the given array nums. We then sort the sorted_arr vector.

We set the starting index to the size of the nums array as a default value. Similarly, the ending index is set to 0.

We then iterate through the nums array and compare each element with the same element in the sorted_arr array. If the elements are not equal, we update our starting and ending indices accordingly.

Finally, we check if the difference between the starting and the ending index is less than or equal to 0. If yes, we return 0 as the whole array is already sorted. Otherwise, we return the length of the subarray.

Time complexity:

The time complexity of this solution is O(nlogn) since we are using the sort function, which has a time complexity of O(nlogn). The iteration over the nums array has a time complexity of O(n), which is not the dominant factor here.

Space complexity:

The space complexity is O(n) since we are creating a new vector for copying the given array nums.

1