Minimum Window Sort

Given an array, find the length of the smallest subarray which when sorted will sort the whole array.

Example 1

Input: [1, 5, 4, 3, 10]
Output: 3
Explanation: We need to sort only the subarray [5, 4, 3] to make the whole array sorted

Example 2

Input: [1, 11, 5, -1, 10]
Output: 5
Explanation: We need to sort the whole array.

We can think of this as two related problems

• How do we find the start of the smallest unsorted subarray?
• How do we find the end of the smallest unsorted subarray?

How to find the start of the unsorted subarray

Let's start with the trivial check. Go through the array from the beginning and find the first place where the left side of the array is larger than the right side.

[1, 5, 4, 3, 10]
[1, (5, 4, 3, 10]

Explanation: Because 5 is larger than 4 we take a guess that the smallest unsorted subarray starts at 5.
             In this case our algorithm is correct.
             It didn't include 1 in the subarray.

[1, 11, 5, -1, 10]
[1, (11, 5, -1, 10]

Explanation: Because 11 is larger than 5 we take a guess that the smallest unsorted subarray starts at 11.
             In this case our algorithm is incorrect. 
             It didn't take into account that within the subarray, the value -1 is smaller than 1.

The thing that works with the trivial solution is that it correctly picks the shortest subarray when the subarray does not contain a global minimum. We can improve on this solution by finding the minimum within the proposed subarray and using that knowledge to extend the proposed start as required.

To do this we re-iterate the array and find the first element that is less than the subarray mininimum. That place is now the start of the subarray.

Now we do the same with the maximum from right to left and we can determine the length of the smallest subarray.