Design Gurus Logo
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:

Image

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).