Scribble 8: Smallest Unsorted Subarray

Here’s the problem statement:

Given an array of integers find the length of the smallest subarray which when sorted will make the entire array sorted in the ascending order.

Let’s dive into the solution:

Loop through the array from the left to the right and find the smallest and the largest elements in the array that are out of order. (An element array[i] is said to be in the ascending order if array[i]>array[i-1] and array[i]<array[i+1])

Note that all those elements in the array that must lie after the minimum out of order element and before the maximum out of order element in the sorted array are also right now in the wrong positions and will need to be re-positioned too. Therefore, we need to find out where in the sorted array must these 2 elements: the minimum out of order element and the maximum out of order element be placed. Those 2 indices will represent the beginning and the ending respectively of the smallest subarray which when sorted which will make the entire array sorted in the ascending order.

To find the correct position of the minimum out of order element in the complete array: loop over the array from the left to the right and find the first element that is > the minimum out of order element. Similarly, to find the correct position of the maximum out of order element in the complete array: loop over the array from the right to the left and find the first element that is < the maximum out of order element.

Time complexity: Every array element is visited once while finding the minimum and the maximum out of order elements in the original array and then some elements are visited once again while finding the correct positions of the minimum and the maximum out of order elements in the sorted array. Since every element is thus visited at max 1 or 2 times so the time complexity is O(N).

Space complexity: O(1) because we do not use any extra storage space

Here’s the code for this solution in Java:

public int smallestUnsortedSubarray(int[] array) {

    int min, max;
    min = Integer.MAX_VALUE;
    max = Integer.MIN_VALUE;
    
    for(int i =0;i<array.length;i++)
    {
        boolean isInOrder = (i==0 || array[i]>=array[i-1])
                                        &&
                            (i==array.length-1 || array[i]<=array[i+1]);
        
        if(!isInOrder) {
            min = Math.min(min, array[i]);
            max = Math.max(max, array[i]);
        }
    }
    if(max == Integer.MIN_VALUE && min == Integer.MAX_VALUE)//i.e. the entire array is already sorted
        return 0;
    int beg, end;
    beg = end = 0;
    for(int i = 0;i<array.length;i++)
    {
        if(array[i]>min) {
            beg = i;
            break;
        }
    }
    for(int i = array.length-1;i>=0;i--)
    {
        if(array[i]<max) {
            end = i;
            break;
        }
    }
    return end-beg+1;
}

Please do let me know if you find this article useful. Also, it’ll be great if you’d provide some feedback. To reach out, please leave a comment in the Contact section. Thanks! Happy Coding! 🙂