Last Updated: 20 Aug, 2021

Find The Minimum Length

Moderate

Asked in company

Solve now

Problem statement

You and Ram are friends who just started coding. You both took part in a coding competition. To win it, you have to solve a particular problem. You have given an array ‘ARR’ of integers. Find the minimum length of a subarray such that choosing this subarray will make the whole array sorted in ascending order.

Example :

Given ‘ARR’ : {1, 3, 2, 4, 5}
Selecting subarray {3, 2} and sorting it will make the whole array sorted.
Resultant ‘ARR’ : {1, 2, 3, 4, 5} 

So, the minimum length will be 2.

Input Format :

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

The first line of each test case contains a single integer ‘N’ representing the size of the array.

The second line contains 'N' single space-separated integers representing the elements of the array.

Output Format :

For each test case, print a single integer representing the size of the subarray.

Print the output of each test case in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= N <= 2*10^3
1 <= ARR[i] <= 5*10^3

Time Limit : 1 sec

Solve now

Approaches

01 Approach

The basic idea is to create a copy of the given array and sort it. Then, by comparing the elements of both of the arrays, we can find the leftmost and rightmost mismatched elements.

Here is the algorithm :

Create a copy of the array ‘ARR’ (say, ‘arrCopy’).
Sort the array ‘arrCopy’.
Create two variables (say, ‘START’ and ‘END’) which will be used to store the starting and ending point of the subarray respectively and initialize them as ‘N’ and 0.
Run a loop from 0 to ‘N’ - 1 (say, iterator ‘i’).
Check if ‘arrCopy[i]’ is not equal to ‘ARR[i]’.
- Update ‘START’ as minimum of ‘START’ and ‘i’.
- Update ‘END’ as maximum of ‘END’ and ‘i’.
Check if ‘END’ is greater than ‘START’
- Return ‘END’ - ‘START’ + 1.
Else
- Return 0. (No such subarray exists )

Solve now

02 Approach

The approach is to find the index of the leftmost element which is greater than its next element and similarly to find the index of the rightmost element which is smaller than its previous element. We also need to check whether the minimum element present in the subarray is not smaller than any element present in the prefix part (excluding the part of subarray) of the array. Similarly, we need to check for the suffix part also.

Here is the algorithm :

Create two variables (say, ‘START’ and ‘END’) which will be used to store the starting and ending point of the subarray respectively and initialize them with -1.
Run a loop from 0 to ‘N’ - 2 (say, iterator ‘i’).
Check if ‘ARR[i]’ is greater than ‘ARR[i + 1]’.
- Update ‘START’ as ‘i’ and break out of the loop.
If ‘START’ is equal to -1 ( already sorted ), return 0.
Run a loop from ‘N’ - 1 to 1.
Check if ‘ARR[i]’ is smaller than ‘ARR[i - 1]’
- Update ‘END’ as ‘i’ and break out of the loop.
Create two variables (say, ‘MAX’ and ‘MIN’) which will store the maximum and minimum values of the subarray.
Run a loop from 0 to ‘START’ (say, iterator ‘i’)
Check if ‘ARR[i]’ is greater than ‘MIN’.
- Update ‘START’ as ‘i’ and break out of the loop.
Run a loop from ‘N’ - 1 to ‘END’ + 1.
Check if ‘ARR[i]’ is smaller than ‘MAX’
- Update ‘END’ as ‘i’ and break out of the loop.
Check if ‘END’ is greater than ‘START’
- Return ‘END’ - ‘START’ + 1.
Else
- Return 0. (No such subarray exists)

Solve now