Shortest Unsorted Continuous Subarray
In this post, I will be explaining my solution to one of the Leetcode algorithmic problems for February 2021 monthly challenge.
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.
SOLUTION
As can be seen from the above image, a Shortest Continuous Subarray is the shortest unsorted subarray of an array that when sorted would leave the whole array sorted in that order. For example, in the array {1,2,3,4,6,7,8,10,9,5,11,15}, the shortest subarray we can sort to keep the whole array sorted in ascending order is subarray starting from index 4 to index 9 i.e. {6,7,8,10,9,5}, hence the solution is 6, which is the length of the subarray.
Can you think of any solution to this problem? Of course, the Brute-force approach.
BRUTE-FORCE APPROACH
Surprisingly, even the supposedly easy brute-force approach is not readily intuitive in this case. What do you think would be the brute-force solution to this problem? The following steps explains what I take as the brute-force approach:
1. For each value in the array, say current value;
2. Find the index of the first value in the array that is larger than the current value if it exits, starting from the beginning of the array to the location of the current value. If the index exists, let’s call it left_index.
3. Also, find the index of the first value in the array that is smaller than the current value, if it exists, starting from the end of the array to the location of the current value. If the index exists, let’s call it right_index.
4. Find all the existing left_index and right_index with respect to all the entries in the array. Let’s min_left represent the min of all left_indexes and min_right the max of all right_indexes. the subarray [min_left, min_right is the shortest unsorted continuous subarray of the original array. If no left_index and right_index exist, then the array is already sorted in ascending order.
For example, consider the array {11,12,13,16,15,14,17,19}. Let’s perform the above steps on the array from indexes i=0 to 7:
When i= 0 with value 11: There is no value to left of 11 which is greater than 11 and there is no value to the right of 11 which is smaller than 11, hence no left_index and no right_index.
When i=1 with value 12: No left_index and no right_index.
When i=2 with value 13: No left_index and no right_index.
When i=3 with value 16: No left_index, But right_index = 5(because 14, which is at index 5 from the beginning of the array, is the first element that is smaller than 16.
When i=4 with value 15: left_index = 3(because 16, which is at index 3, is the first element from the beginning of the array, that is smaller than 15). Also right_index = 5.
When i=5 with value 14: left_index = 3 but no right_index.
When i=6 with value 17: no left_index and no right_index.
When i=7 with value 19: no left_index and no right_index.
The min of all left_indexes is 3 while the max of all right_indexes is 5, hence the shortest unsorted continuous subarray is [3, 5]. You can confirm this by looking at the values in the subarray [3,5] of the given array in the example, which are {16,15,14}. Notice that this subarray is not sorted in ascending order and if it become sorted in ascending order, then the given array would be sorted in ascending order too.
Below is the code implementation of the above approach in Java.
ANALYSIS OF THE BRUTE-FORCE APPROACH
The time complexity of the brute-force approach is O(N²). Notice that the worst case of the approach occurs when the original array is already sorted in ascending order. In such case, for every entries, the whole array is checked for the left_index and right_index. No auxiliary memory was used.
APPROACH 2: PREPROCESSING AND 2-POINTERS TECHNIQUE
This approach has only 2 major steps;
1. Given an array say arr, iterate the given array once and find all occurrences of this format: arr[i] > a[j] for all i < j ,where a[j] is the smaller value and a[i] is the larger value. Keep track of the minimum of all a[j] as min and maximum of all a[i] as max. If there is no such occurrence, then the given array is already sorted in ascending order.
2. Using the min and max obtained in Step 1, employ 2-pointer technique to find the index (say left)of the first element in the given array from the beginning, which is greater than min. Also, find the index (say right) of the first element in the given array from the end, which is smaller than max.
The subarray [left, right] is the shortest unsorted continuous subarray of the given array.
ANALYSIS OF THE SECOND APPROACH
The time complexity of the second approach is O(N) where N is the length of the given array. Notice that we only linearly iterated the array twice — to find the min and max elements at locations where there are mismatched arrangements, then using 2-pointers technique to find the right locations of min and max. No auxiliary space used.
Below is the code implementation of the second approach in Java.
Conclusive Remark:
Thank you for checking out this post. If you have any comment or suggestion, please let me know in the comment sections. :-)
