Sub Sort
You are given an integer array ‘ARR’. You have to find the length of the shortest contiguous subarray such that, if you sort this subarray in ascending order, then the whole array will be sorted in ascending order.

An array 'C' is a subarray of array 'D' if it can be obtained by deletion of several elements(possibly zero) from the beginning and the end from array 'D'.

Example:

Let’s say we have an array 'ARR' {10, 12, 20, 30, 25, 40, 32, 31, 35, 50, 60}. Then we have to find the subarray {30 , 25 , 40 , 32 , 31 , 35} and print its length = 5 as our output. Because, when we sort this subarray the whole array will be sorted.

Input format:

The very first line of input contains an integer ‘T’ denoting the number of test cases. The first line of every test case contains one integer ‘N’ denoting the number of elements present in the array. The second line of every test case contains ‘N’ space-separated integers denoting the elements present in the array.

Output format:

For each test case, print the shortest length of the unsorted subarray. Output for each test case is printed on a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just return the length of the shortest subarray.

Constraints:

1

Question

Sub Sort

You are given an integer array ‘ARR’. You have to find the length of the shortest contiguous subarray such that, if you sort this subarray in ascending order, then the whole array will be sorted in ascending order.

An array 'C' is a subarray of array 'D' if it can be obtained by deletion of several elements(possibly zero) from the beginning and the end from array 'D'.

Example:

Let’s say we have an array 'ARR' {10, 12, 20, 30, 25, 40, 32, 31, 35, 50, 60}. Then we have to find the subarray {30 , 25 , 40 , 32 , 31 , 35} and print its length = 5 as our output. Because, when we sort this subarray the whole array will be sorted.

Input format:

The very first line of input contains an integer ‘T’ denoting the number of test cases. 

The first line of every test case contains one integer ‘N’ denoting the number of elements present in the array.

The second line of every test case contains ‘N’ space-separated integers denoting the elements present in the array.

Output format:

For each test case, print the shortest length of the unsorted subarray. Output for each test case is printed on a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just return the length of the shortest subarray.

Constraints:

1 <= T <= 10
1 <= N <= 5 * 10 ^ 4
-10^5 <= ARR[i] <= 10^5

Where  ‘T’ represents the number of test cases, ‘N’ represents the number of elements present in the array, and ‘ARR[i]’ represents the array element. 

Time Limit: 1sec

Accepted Answer

The question asks to find the length of the shortest contiguous subarray that needs to be sorted in order to sort the whole array.

Iterate through the array and find the first element that is out of order from the left side.
Iterate through the array and find the first element that is out of order from the right side.
Find the minimum and maximum element within the subarray from the above steps.
Expand the subarray from both sides until all elements within the subarray are in the correct order.
Return the length of the subarray.

Accepted Answer

Brute Force

In this approach, we consider every possible subarray that can be formed from the given array ‘ARR’. For every subarray ARR[i … j] considered, we need to check whether this is the smallest unsorted subarray or not.

The algorithm is as follows:

Let’s take the variable ‘ANS’ equal to 'N' (the length of the array) initially.
Now for every subarray ARR[i … j], we will find the maximum and minimum value lying in that subarray given by ‘MAXELEMENT’ and ‘MINELEMENT’ respectively.
Further, we have to check that every element in ARR[0 … i-1] should be lesser than the ‘MINELEMENT’.
And similarly every element in ARR[j+1 …. N-1] should be greater than the ‘MAXELEMENT’.
The above two steps are performed to check whether the subarray ARR[0 … i-1] and subarray ARR[j+1 … N-1] are sorted because then only ARR[i ... j] could be our required subarray.
If all conditions are met, then ('j' - 'i' + 1) will be the required length.
The same process will be repeated for every subarray chosen and the smallest unsorted subarray is determined.

Space Complexity: O(1)Explanation:

O(1)

As constant space is required.

Time Complexity: O(n^3)Explanation:

O(N^3), where N is the number of elements in the array.

Considering every subarray will take O(N^2) time and checking whether this subarray is the required subarray will take O(N) time. Thus, the final time complexity will be O(N^3).

C++ (g++ 5.4)

/*

    Time complexity: O(N^3)

    Space Complexity: O(1)



    Where N is the number of elements in the array.

*/



#include



int subarraySort(vector &arr) {

    int ans = arr.size();

    int n = arr.size();



    for (int i = 0 ; i < n ; i++) {

        for (int j = i ; j <= n ; j++) {



            // For every subarray arr[i...j].

            int minElement = INT_MAX , maxElement = INT_MIN , prev = INT_MIN;



            // Find the minimum and maximum element in subarray arr[i..j].

            for (int k = i ; k < j ; k++) {

                minElement = min(minElement , arr[k]);

                maxElement = max(maxElement , arr[k]);

            }



            // Check that all the elements in subarray arr[0..i-1] are smaller than minumim element.

            if ((i > 0 && arr[i - 1] > minElement) || (j < n && arr[j] < maxElement)) {

                continue;

            }



            int k = 0;

            while (k < i && prev <= arr[k]) {

                prev = arr[k];

                k++;

            }

            if (k != i) {

                continue;

            }



            // Check that all the elements in subarray arr[j..n-1] are greater than maximum element.

            k = j;

            while (k < n && prev <= arr[k]) {

                prev = arr[k];

                k++;

            }



            // Shortest unsorted subarray would be chosen.

            if (k == n) {

                ans = min(ans , j - i);

            }

        }

    }

    return ans;

}

Java (SE 1.8)

/*
    Time complexity: O(N^3)
    Space Complexity: O(1)

    Where N is the number of elements in the array.
*/

import java.util.ArrayList;

public class Solution {
    public static int subarraySort(ArrayList arr) {
        int ans = arr.size();
        int n = arr.size();

        for (int i = 0 ; i < n ; i++) {
            for (int j = i ; j <= n ; j++) {

                // For every subarray arr[i...j].
                int minElement = Integer.MAX_VALUE , maxElement = Integer.MIN_VALUE , prev = Integer.MIN_VALUE;

                // Find the minimum and maximum element in subarray arr[i..j].
                for (int k = i ; k < j ; k++) {
                    minElement = Math.min(minElement , arr.get(k));
                    maxElement = Math.max(maxElement , arr.get(k));
                }

                // Check that all the elements in subarray arr[0..i-1] are smaller than minumim element.
                if ((i > 0 && arr.get(i - 1) > minElement) || (j < n && arr.get(j) < maxElement)) {
                    continue;
                }

                int k = 0;
                while (k < i && prev <= arr.get(k)) {
                    prev = arr.get(k);
                    k++;
                }
                if (k != i) {
                    continue;
                }

                // Check that all the elements in subarray arr[j..n-1] are greater than maximum element.
                k = j;
                while (k < n && prev <= arr.get(k)) {
                    prev = arr.get(k);
                    k++;
                }

                // Shortest unsorted subarray would be chosen.
                if (k == n) {
                    ans = Math.min(ans , j - i);
                }
            }
        }
        return ans;
    }
}

Python (3.5)

'''
    Time complexity: O(N^3)
    Space Complexity: O(1)

    Where N is the number of elements in the array.
'''

from sys import maxsize

def subarraySort(arr):
    ans = len(arr)
    n = len(arr)

    for i in range(n):
        for j in range(i, n+1):
            # For every subarray arr[i...j].
            minElement = maxsize
            maxElement = -maxsize
            prev = -maxsize

            # Find the minimum and maximum element in subarray arr[i..j].
            for k in range(i, j):
                minElement = min(minElement, arr[k])
                maxElement = max(maxElement, arr[k])

            # Check that all the elements in subarray arr[0..i-1] are smaller than minumim element.
            if ((i > 0 and arr[i - 1] > minElement) or (j < n and arr[j] < maxElement)):
                continue

            k = 0
            while (k < i and prev <= arr[k]):
                prev = arr[k]
                k += 1

            if (k != i):
                continue

            # Check that all the elements in subarray arr[j..n-1] are greater than maximum element.
            k = j
            while (k < n and prev <= arr[k]):
                prev = arr[k]
                k += 1

            # Shortest unsorted subarray would be chosen.
            if (k == n):
                ans = min(ans, j - i)

    return ans

Accepted Answer

Selection Sort

This approach is based on the idea of selection sort. But instead of swapping as we do in the case of selection sort, we will determine the leftmost boundary of the unsorted array and the rightmost boundary of the unsorted subarray.

The algorithm is as follows:

Let’s take two variables ‘START’ and ‘END’ where ‘START’ will be the leftmost boundary of the unsorted subarray and the ‘END’ will be the rightmost boundary of the unsorted subarray.
Here we will use two nested for loops where the outer loop starts from ‘i’ = 0 to ‘i’ = length of array - 2 and inner loop traverses from ‘j’ = ‘i’ + 1 to ‘j’ = length of array - 1.
Now for every ‘ARR[i]’, we will check if any of ‘ARR[j]’ is less than that of ‘ARR[i]’, which means both ‘ARR[i]’ and ‘ARR[j]’ are not at their correct sorted position.
The position of ‘ARR[i]’ (that is i) and ‘ARR[j]’ (that is j) will now mark the boundary of the unsorted array for the time being.
Now after considering all the ‘ARR[i]’ we will take the leftmost ith index which is not at its correct position.
And similarly out of all ‘ARR[j]’ for each of ‘ARR[i]’ we will take the rightmost jth index which is not at its correct position.
It will be achieved by ‘START’ = min('START' , ‘i’) and ‘END’ = max('END' , ‘j’) if ('ARR[j]' < 'ARR[i]').
Finally return the answer as ('END' - ‘START’ + 1) if ('END' >= ‘START’) otherwise return 0.

Space Complexity: O(1)Explanation:

O(1)

As constant space is required.

Time Complexity: O(n^2)Explanation:

O(N^2), where N is the number of elements in the array.

Considering every index i in the array will take O(N) time. For every index chosen, we are making (N - i) comparisons which will take O(N) time. Thus final complexity will be O(N^2).

Java (SE 1.8)

/*
    Time Complexity: O(N^2)
    Space Complexity: O(1)

    Where N is the number of elements in the array.
*/

import java.util.ArrayList;

public class Solution {
    public static int subarraySort(ArrayList arr) {
        int n = arr.size();

        // Declaring two variables start and end.
        int start = n , end = 0;

        for (int i = 0 ; i < n - 1 ; i++) {
            for (int j = i + 1 ; j < n ; j++) {
                /*
                    Now for every arr[i] we will check if any of arr[j] is less than that of arr[i] ,
                    means both arr[i] and arr[j] are not at their correct sorted position.
                    These two elements will now mark the boundary of the unsorted array for the time being.
                */
                if (arr.get(j) < arr.get(i)) {

                    // Finding the leftmost boundary.
                    start = Math.min(start , i);

                    // Finding the rightmost boundary.
                    end = Math.max(end , j);
                }
            }
        }
        if (end >= start) {
            return (end - start + 1);
        }
        else {
            return 0;
        }
    }
}

Python (3.5)

'''
    Time Complexity: O(N^2)
    Space Complexity: O(1)

    Where N is the number of elements in the array.
'''

def subarraySort(arr):
    n = len(arr)

    # Declaring two variables start and end.
    start = n
    end = 0

    for i in range(n-1):
        for j in range(i+1, n):
            '''
                Now for every arr[i] we will check if any of arr[j] is less than that of arr[i] ,
                means both arr[i] and arr[j] are not at their correct sorted position.
                These two elements will now mark the boundary of the unsorted array for the time being.
            '''
            if (arr[j] < arr[i]):
                # Finding the leftmost boundary.
                start = min(start, i)

                # Finding the rightmost boundary.
                end = max(end, j)

    if (end >= start):
        return (end - start + 1)
    else:
        return 0

C++ (g++ 5.4)

/*

    Time Complexity: O(N^2)

    Space Complexity: O(1)



    Where N is the number of elements in the array.

*/



int subarraySort(vector &arr) {

    int n = arr.size();



    // Declaring two variables start and end.

    int start = n , end = 0;



    for (int i = 0 ; i < n - 1 ; i++) {

        for (int j = i + 1 ; j < n ; j++) {

            /*

               Now for every arr[i] we will check if any of arr[j] is less than that of arr[i] ,

               means both arr[i] and arr[j] are not at their correct sorted position.

               These two elements will now mark the boundary of the unsorted array for the time being.

            */

            if (arr[j] < arr[i]) {



                // Finding the leftmost boundary.

                start = min(start , i);



                // Finding the rightmost boundary.

                end = max(end , j);

            }

        }

    }

    if (end >= start) {

        return (end - start + 1);

    }

    else {

        return 0;

    }

}

Accepted Answer

Sorting

This approach is based on the idea of sorting. Here we will copy the given array in another array and then sort it and then compare this array with the given array. We will determine the leftmost and the rightmost position, where the element at this position mismatches. And the subarray lying between these two positions is the unsorted subarray.

The algorithm is as follows:

Make an array ‘COPY’ of the same size as that of the original array and copy all the elements from array ‘ARR’ into array ‘COPY’.
Next sort the array ‘COPY’ in ascending order.
Take two variables ‘START’ = length of the array and ‘END’ = 0.
Now traverse the array ‘COPY’ and whenever there is a mismatch between the elements of array ‘ARR’ and array ‘COPY’, then ‘START’ = min('START', ‘i’) and ‘END’ = max('END', ‘i’).
The ‘START’ and the ‘END’ variables mark the leftmost and the rightmost indices of the unsorted subarray.
Then finally return the answer, if ('END' > ‘START’) return ('END' - ‘START’ + 1), otherwise return 0.

Space Complexity: O(n)Explanation:

O(N), where N is the number of elements in the array.

O(N) extra space is required for the temporary array. Hence, the overall space complexity is O(N).

Time Complexity: O(nlogn)Explanation:

O(N*log(N)), where N is the number of elements in the array.

Making a ‘copy’ array and sorting it will take O(N*log(N)) time. Also traversing the array to find the mismatched indices will take O(N) time. So, the final time complexity will be O(N + N*log(N)) = O(N*log(N)).

Python (3.5)

'''
    Time complexity: O(N*log(N))
    Space Complexity: O(N)

    Where N is the number of elements in the array.
'''

from copy import deepcopy

def subarraySort(arr):
    n = len(arr)

    # Take another array copy where you will copy all the elements of original array.
    copy = deepcopy(arr)

    # Sort the copied array in ascending order.
    copy.sort()

    # Declare two variables start and end to find the boundary.
    start = n
    end = 0

    # Now check for mismatch between the elements in copied array and original array.
    for i in range(n):
        
        if (copy[i] != arr[i]):

            # Leftmost boundary.
            start = min(start, i)

            # Rightmost boundary.
            end = max(end, i)

    if (end >= start):
        return (end - start + 1)
    else:
        return 0

Java (SE 1.8)

/*
    Time complexity: O(N*log(N))
    Space Complexity: O(N)

    Where N is the number of elements in the array.
*/

import java.util.ArrayList;
import java.util.Collections;

public class Solution {
    public static int subarraySort(ArrayList arr) {
        int n = arr.size();

        // Take another array copy where you will copy all the elements of original array.
        ArrayList copy = new ArrayList();
        for (int i = 0 ; i < n ; i++) {
            copy.add(arr.get(i));
        }

        Collections.sort(copy);

        // Declare two variables start and end to find the boundary.
        int start = n , end = 0;

        // Now check for mismatch between the elements in copied array and original array.
        for (int i = 0 ; i < n ; i++) {

            if (copy.get(i) != arr.get(i)) {

                // Leftmost boundary.
                start = Math.min(start , i);

                // Rightmost boundary.
                end = Math.max(end , i);
            }
        }

        if (end >= start) {
            return end - start + 1;
        }
        else {
            return 0;
        }
    }
}

C++ (g++ 5.4)

/*

    Time complexity: O(N*log(N))

    Space Complexity: O(N)



    Where N is the number of elements in the array.

*/



#include



int subarraySort(vector &arr) {

    int n = arr.size();



    // Take another array copy where you will copy all the elements of original array.

    vector copy;

    for (int i = 0 ; i < n ; i++) {

        copy.push_back(arr[i]);

    }



    // Sort the copied array in ascending order.

    sort(copy.begin() , copy.end());



    // Declare two variables start and end to find the boundary.

    int start = n , end = 0;



    // Now check for mismatch between the elements in copied array and original array.

    for (int i = 0 ; i < n ; i++) {



        if (copy[i] != arr[i]) {



            // Leftmost boundary.

            start = min(start , i);



            // Rightmost boundary.

            end = max(end , i);

        }

    }



    if (end >= start) {

        return end - start + 1;

    }

    else {

        return 0;

    }

}

Accepted Answer

Sub Sort

This approach uses two passes of the array. In the first pass, Iterate from the end, and check whether the array is in descending order, i.e., ARR[i] > ARR[i-1] > ARR[i-2] > … . If not we will find the minimum index at which the condition breaks. In the second pass, Iterate from the start, and check whether the array is in ascending order, i.e., ARR[i] < ARR[i+1] < ARR[i+2] < …. If not we find the maximum index at which the condition breaks.

The algorithm is as follows:

Create a ‘START’ and ‘END’ variable to store the indexes of starting and ending positions of the shortest unsorted contiguous subarray respectively.
Make a variable ‘CURMIN’ and initialize it with an infinite value.
Iterate from the end of the array, and check whether the element at index ‘i’ is less than ‘curMin’ or not.
- If it is less than ‘CURMIN’, then update ‘CURMIN’ to this ‘ARR[i]’.
- Else, update ‘START’ to ‘i’.
Make a variable ‘CURMAX’ and initialize it with a negative infinite value.
Iterate from the start of the array, and check whether the element at index ‘i’ is greater than 'CURMAX' or not.
- If it is more than ‘CURMAX’, then update ‘CURMAX’ to this ‘ARR[i]’.
- Else, update ‘END’ to ‘i’.
In the end check for a valid start index, which means if ('START' == -1) then return 0 otherwise return ('END' - ‘START’ + 1).

Example:

Let's say we have an array ARR = {2, 6, 4, 8,10,9,15} (consider 0 based indexing).

Here n = 7 , start = -1 , end = n

Also curMin = inf curMax = -inf

Now first traverse the array from right to left we have two conditions:

First: if(curMin > Arr[i]) then curMin = Arr[i]

Second: if(Arr[i] > curMin) then update start = i

For i = 6 (Arr[6] = 15) :

curMin = 15

start = -1

For i = 5 (Arr[5] = 9) :

curMin = 9

start = -1

For i = 4 (Arr[4] = 10) :

curMin = 15

start = 4

For i = 3 (Arr[3] = 8) :

curMin = 8

start = 4

For i = 2 (Arr[2] = 4) :

curMin = 4

start = 4

For i = 1 (Arr[1] = 6) :

curMin = 4

start = 1

For i = 0 (Arr[0] = 2) :

curMin = 2

start = 1

Now traverse the array from left to right we have two conditions:

First: if(curMax < Arr[i]) then curMax = Arr[i]

Second: if(Arr[i] < curMax) then end = i

For i = 0 (Arr[0] = 2) :

curMax = 2

end = 7

For i = 1 (Arr[1] = 6) :

curMax = 6

end = 7

For i = 2 (Arr[2] = 4) :

curMax = 6

end = 2

For i = 3 (Arr[3] = 8) :

curMax = 8

end = 2

For i = 4 (Arr[4] = 10) :

curMax = 10

end = 2

For i = 5 (Arr[5] = 9) :

curMax = 10

end = 5

For i = 6 (Arr[6] = 15) :

curMax = 15

end = 5

At the end, we have ‘start’ = 1 and ‘end’ = 5

Hence subarray will be { 6, 4, 8,10,9}

Space Complexity: O(1)Explanation:

O(1).

As constant space is used.

Time Complexity: O(n)Explanation:

O(N), where N is the number of elements in the array.

We are traversing the given array to find the ‘start’ and ‘end’ index and traversing takes O(N) time. Thus the final complexity will be O(N + N) = O(N).

Python (3.5)

'''
    Time complexity: O(N)
    Space Complexity: O(1)

    Where N is the number of elements in the array.
'''

from sys import maxsize

def subarraySort(arr):
    n = len(arr)

    start = -1
    end = n

    '''
        Iterate from the end, and check weather the element at index 
        "i" is the current minimum element or not.
        If not then "i" is the starting index.
    '''

    curMin = maxsize
    for i in range(n-1, -1, -1):
        if (curMin > arr[i]):
            curMin = arr[i]

        if (arr[i] > curMin):
            start = i

    '''
        Iterate from the start, and check weather the element at index 
        "i" is the current maximum element or not.
        If not then "i" is the ending index.
    '''

    curMax = -maxsize
    for i in range(n):
        if (curMax < arr[i]):
            curMax = arr[i]
        if (arr[i] < curMax):
            end = i

    # If no starting index found, that means the array is already sorted in ascending order.
    if (start == -1):
        return 0

    return (end - start + 1)

C++ (g++ 5.4)

/*

    Time complexity: O(N)

    Space Complexity: O(1)



    Where N is the number of elements in the array

*/



#include



int subarraySort(vector &arr) {

    int n = arr.size();

    int start = -1, end = n;



    /*

        Iterate from the end, and check weather the element at index 

        "i" is the current minimum element or not.

        If not then "i" is the starting index.

    */

    int curMin = INT_MAX;

    for (int i = n - 1; i >= 0; i--) {

        if (curMin > arr[i]) {

            curMin = arr[i];

        }



        if (arr[i] > curMin) {

            start = i;

        }

    }



    /*

        Iterate from the start, and check weather the element at index 

        "i" is the current maximum element or not.

        If not then "i" is the ending index.

    */

    int curMax = INT_MIN;

    for (int i = 0; i < n; i++) {

        if (curMax < arr[i]) {

            curMax = arr[i];

        }



        if (arr[i] < curMax) {

            end = i;

        }

    }



    // If no starting index found, that means the array is already sorted in ascending order.

    if (start == -1) {

        return 0;

    }

    return end - start + 1;

}

Java (SE 1.8)

/*
    Time complexity: O(N)
    Space Complexity: O(1)

    Where N is the number of elements in the array
*/

import java.util.ArrayList;

public class Solution {
    public static int subarraySort(ArrayList arr) {
        int n = arr.size();
        int start = -1, end = n;

        /*
            Iterate from the end, and check weather the element at index 
            "i" is the current minimum element or not.
            If not then "i" is the starting index.
        */
        int curMin = Integer.MAX_VALUE;
        for (int i = n - 1; i >= 0; i--) {
            if (curMin > arr.get(i)) {
                curMin = arr.get(i);
            }

            if (arr.get(i) > curMin) {
                start = i;
            }
        }

        /*
            Iterate from the start, and check weather the element at index 
            "i" is the current maximum element or not.
            If not then "i" is the ending index.
        */
        int curMax = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            if (curMax < arr.get(i)) {
                curMax = arr.get(i);
            }

            if (arr.get(i) < curMax) {
                end = i;
            }
        }

        // If no starting index found, that means the array is already sorted in ascending order.
        if (start == -1) {
            return 0;
        }
        return end - start + 1;
    }
}

You are given an integer array ‘ARR’. You have to find the length of the shortest contiguous subarray such that, if you sort this subarray in ascending order, then the whole array will be sorted in ascending order.

An array 'C' is a subarray of array 'D' if it can be obtained by deletion of several elements(possibly zero) from the beginning and the end from array 'D'.

Example:

Input format:

Output format:

Note:

Constraints:

Top ZeMoSo Technologies Associate Software Engineer interview questions & answers

Popular interview questions of Associate Software Engineer