Find The Minimum Length

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
3 upvotes
Asked in company
Microsoft

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
4 
1 3 2 4
6
2 6 5 1 9 10
Sample Output 1 :
2
4
Explanation For Sample Input 1 :
For first test case :

Choosing subarray {3, 2} and sorting it will result in a sorted array.
Resultant array : {1, 2, 3, 4}.

For second test case :

Choosing subarray {2, 6, 5, 1} and sorting it will result in a sorted array.
Resultant array : {1, 2, 5, 6, 9, 10}.
Hint

Think of sorting the array.

Approaches (2)
Sorting

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 :
 

  1. Create a copy of the array ‘ARR’ (say, ‘arrCopy’).
  2. Sort the array ‘arrCopy’.
  3. 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.
  4. Run a loop from 0 to ‘N’ - 1 (say, iterator ‘i’).
  5. 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’.
  6. Check if ‘END’ is greater than ‘START’
    • Return ‘END’ - ‘START’ + 1.
  7. Else
    • Return 0.  (No such subarray exists )
Time Complexity

O(N*log(N)), where ‘N’ is the size of the array.

 

We are creating a copy of our original array which takes O(N) time and then sorting it which takes O(N*log(N)) time. We also run a loop ‘N’ times to find mismatched elements which takes O(N) time. Therefore, the overall time complexity will be O(N*log(N)).

Space Complexity

O(N), where ‘N’ is the size of the array.

 

We are using an extra space by making an array of size ‘N’. Therefore, the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Find The Minimum Length
Full screen
Console