Solution: Problem Challenge 3: Minimum Window Sort
Go Back

## Problem Statement

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

Example 1:

``````Input: [1, 2, 5, 3, 7, 10, 9, 12]
Output: 5
Explanation: We need to sort only the subarray [5, 3, 7, 10, 9] to make the whole array sorted
``````

Example 2:

``````Input: [1, 3, 2, 0, -1, 7, 10]
Output: 5
Explanation: We need to sort only the subarray [1, 3, 2, 0, -1] to make the whole array sorted
``````

Example 3:

``````Input: [1, 2, 3]
Output: 0
Explanation: The array is already sorted
``````

Example 4:

``````Input: [3, 2, 1]
Output: 3
Explanation: The whole array needs to be sorted.
``````

Constraints:

• 1 <= arr.length <= 10<sup>4</sup>
• -10<sup>5</sup> <= arr[i] <= 10<sup>5</sup>

## Solution

As we know, once an array is sorted (in ascending order), the smallest number is at the beginning and the largest number is at the end of the array. So if we start from the beginning of the array to find the first element which is out of sorting order i.e., which is smaller than its previous element, and similarly from the end of array to find the first element which is bigger than its previous element, will sorting the subarray between these two numbers result in the whole array being sorted?

Let’s try to understand this with Example-2 mentioned above. In the following array, what are the first numbers out of sorting order from the beginning and the end of the array:

``````    [1, 3, 2, 0, -1, 7, 10]
``````

Starting from the beginning of the array the first number out of the sorting order is ‘2’ as it is smaller than its previous element which is ‘3’. Starting from the end of the array the first number out of the sorting order is ‘0’ as it is bigger than its previous element which is ‘-1’ As you can see, sorting the numbers between ‘3’ and ‘-1’ will not sort the whole array. To see this, the following will be our original array after the sorted subarray:

``````    [1, -1, 0, 2, 3, 7, 10]
``````

The problem here is that the smallest number of our subarray is ‘-1’ which dictates that we need to include more numbers from the beginning of the array to make the whole array sorted. We will have a similar problem if the maximum of the subarray is bigger than some elements at the end of the array. To sort the whole array we need to include all such elements that are smaller than the biggest element of the subarray.

### Step-by-step Algorithm

1. Initialize Pointers: Set `low` to 0 and `high` to the last index of the array.
2. Find Left Boundary:
• Move `low` to the right while the current element is less than or equal to the next element.
3. Check If Sorted:
• If `low` reaches the end, the array is already sorted. Return 0.
4. Find Right Boundary:
• Move `high` to the left while the current element is greater than or equal to the previous element.
5. Find Min and Max:
• Iterate from `low` to `high` to find the minimum and maximum values in this subarray.
6. Extend Left Boundary:
• Move `low` to the left while the previous element is greater than the subarray's minimum.
7. Extend Right Boundary:
• Move `high` to the right while the next element is less than the subarray's maximum.
8. Calculate Length:
• The length of the subarray to be sorted is `high - low + 1`.

### Algorithm Walkthrough

Using the input `[1, 3, 2, 0, -1, 7, 10]`:

• Initialize Pointers: `low = 0`, `high = 6`.
• Find Left Boundary:
• Compare `1` and `3`, move `low` to `1`.
• Compare `3` and `2`, stop. `low = 1`.
• Find Right Boundary:
• Compare `10` and `7`, move `high` to `5`.
• Compare `7` and `-1`, move `high` to `4`.
• Compare `-1` and `0`, stop at `4`.
• Find Min and Max:
• Subarray is `[3, 2, 0, -1]`.
• Minimum is `-1`, Maximum is `3`.
• Extend Left Boundary:
• `1` is greater than `-1`, `low` stays `1`.
• Extend Right Boundary:
• `7` is not less than `3`, `high` stays `4`.
• Calculate Length:
• Length is `high - low + 1` = `4 - 0 + 1 = 5`.

Here is the visual representation of this algorithm for Example 1:

## Code

Here is what our algorithm will look like:

Python3
Python3

Time Complexity

The time complexity of the above algorithm will be O(N).

Space Complexity

The algorithm runs in constant space O(1).