Sub Sort

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
6 upvotes
Asked in companies
FreshworksAdobeAmazon

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
3
7
2 6 4 8 10 9 15
4
1 2 3 4
1
1
Sample Output 1:
5
0
0
Explanation For Sample Input 1:
For the first test case, you need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

For the second test case, the array is already sorted. So the answer is 0.

For the third test case, it has one element so it is already sorted. Hence the answer is 0.
Sample Input 2:
2
11
10 12 20 30 25 40 32 31 35 50 60
9
0 1 15 25 6 7 30 40 50
Sample Output 2:
 6
 4
Explanation For Sample Input 2:
For the first test case, you need to sort [30, 25, 40, 32, 31, 35] in ascending order to make the whole array sorted in ascending order.

For the second test case, you need to sort [15, 25, 6, 7] in ascending order to make the whole array sorted in ascending order.
Hint

Can you solve this problem by generating all the subarrays?

Approaches (4)
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:

  1. Let’s take the variable ‘ANS’ equal to 'N' (the length of the array) initially.
  2. 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.
  3. Further, we have to check that every element in ARR[0 … i-1] should be lesser than the ‘MINELEMENT’.
  4. And similarly every element in ARR[j+1 …. N-1] should be greater than the ‘MAXELEMENT’.
  5. 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.
  6. If all conditions are met, then ('j' - 'i' + 1) will be the required length.
  7. The same process will be repeated for every subarray chosen and the smallest unsorted subarray is determined.
Time Complexity

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

Space Complexity

O(1)

 

As constant space is required.

Code Solution
(100% EXP penalty)
Sub Sort
Full screen
Console