Shortest Unsorted Continuous Subarray solution

In this post we will try to come up with a logical and intuitive solution for the question https://leetcode.com/problems/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 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

Example 3:

Input: nums = [1]

Output: 0

Thought Process

We need to find the length of the shortest subarray, such that if we sort that subarray the whole array in turn gets sorted in ascending order.

We know that our end goal is to make the array sorted. For starters, we know for sure that our answer can never exceed the length of the array as we can sort the whole array. But how do we ensure that, it is the shortest subarray ?

Well, as the question talks about sorting, why don’t we start by sorting our nums arrays and then compare with the original array. For this, we create a new array and sort it.

Now when we compare we know for sure, that if elements match at the same index for both the original and sorted array, that element can be neglected as it was already sorted. What we can do is try to find the mismatched indexes and try to form our subarray. This might seem to be correct answer at first but we need to take care of corner case that we can have disjoint mismatch subarrays and thus we need to find the first and the last mismatch index to find the correct subarray length.

Code

Asymptotic Analysis

Time complexity : O(NLogN) as we are sorting the array and we are yet to have a sorting algorithm faster that NLogN as of now :)

Space complexity: O(N) + O(N) = O(N), where first one comes from the the vector we created and other one comes from the sort function which uses merge sort which eventually uses O(N) extra space