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
- Initialize Pointers: Set
low
to 0 andhigh
to the last index of the array. - Find Left Boundary:
- Move
low
to the right while the current element is less than or equal to the next element.
- Move
- Check If Sorted:
- If
low
reaches the end, the array is already sorted. Return 0.
- If
- Find Right Boundary:
- Move
high
to the left while the current element is greater than or equal to the previous element.
- Move
- Find Min and Max:
- Iterate from
low
tohigh
to find the minimum and maximum values in this subarray.
- Iterate from
- Extend Left Boundary:
- Move
low
to the left while the previous element is greater than the subarray's minimum.
- Move
- Extend Right Boundary:
- Move
high
to the right while the next element is less than the subarray's maximum.
- Move
- Calculate Length:
- The length of the subarray to be sorted is
high - low + 1
.
- The length of the subarray to be sorted is
Algorithm Walkthrough
Using the input [1, 3, 2, 0, -1, 7, 10]
:
- Initialize Pointers:
low = 0
,high = 6
. - Find Left Boundary:
- Compare
1
and3
, movelow
to1
. - Compare
3
and2
, stop.low = 1
.
- Compare
- Find Right Boundary:
- Compare
10
and7
, movehigh
to5
. - Compare
7
and-1
, movehigh
to4
. - Compare
-1
and0
, stop at4
.
- Compare
- Find Min and Max:
- Subarray is
[3, 2, 0, -1]
. - Minimum is
-1
, Maximum is3
.
- Subarray is
- Extend Left Boundary:
1
is greater than-1
,low
stays1
.
- Extend Right Boundary:
7
is not less than3
,high
stays4
.
- Calculate Length:
- Length is
high - low + 1
=4 - 0 + 1 = 5
.
- Length is
Here is the visual representation of this algorithm for Example 1:
Code
Here is what our algorithm will look like:
Time Complexity
The time complexity of the above algorithm will be O(N).
Space Complexity
The algorithm runs in constant space O(1).