Sub Sort

Posted: 5 Mar, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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
Approach 1

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.
Try Problem