Sort the Permutation

Moderate
0/80
profile
Contributed by
2 upvotes
Asked in companies
AmazonCIS - Cyber InfrastructureNokia

Problem statement

You are the class teacher and you have a boring duty to get the class arranged according to roll numbers.

There are 'N' students in your class, each student has a roll number between 1 and N. You are also given an array 'ARR' indicating the initial arrangement of the students, and you need to rearrange them so they are sorted by roll number.

In order to make this process more interesting, you come up with an idea! To rearrange the students you can select any student and place him either at the beginning or at the end, and do this until all the students are sorted in increasing order of their roll numbers. You need to find the minimum such steps you need to perform to rearrange the students in increasing order of their roll numbers.

For Example : 
If ‘N’ = 5, ‘ARR’ = {1, 2, 4, 5, 3}

You can sort the given arrangement in two steps. 

In the first step select the student with roll number 4 (ARR[2]) and place him at the end, the arrangement now becomes: {1, 2, 3, 5, 3, 4}. In the second step select the student with roll number 5 (ARR[3]) and place him at the end, resulting in the arrangement: {1, 2, 3, 4, 5} which is in sorted order.

It is not possible to sort the given arrangement in less than two steps, therefore we will print 2.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:

The first line of each test case contains a single integer ‘N’, denoting the number of students in the class.

The second line of each test case contains N integers ‘ARR’, denoting the initial arrangement of the students, each array element denotes the roll number of one of the students.
Output Format : 
For each test case, print the minimum steps required to rearrange the students.

Output for each test case will be printed in a separate line.
Note : 
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints : 
1 ≤ T ≤ 10      
1 ≤ N ≤ 20000
1 ≤ ARR[i] ≤ N

Time limit: 1 sec
Sample Input 1 :
2
5
1 2 4 5 3
4
1 2 3 4
Sample Output 1 :
2
0
Explanation For Sample Input 1 :
For test case 1 :
We will print 2 because:
In the first step, we can select the student with roll number 4 (ARR[2]) and place him at the end, the arrangement now becomes: {1, 2, 3, 5, 3, 4}. In the second step select the student with roll number 5 (ARR[3]) and place him at the end, resulting in the arrangement: {1, 2, 3, 4, 5} which is in sorted order. Therefore we need at least two steps to rearrange the students.

For test case 2 : 
We will print 0 because:
The given arrangement is already sorted and no rearrangements are needed.
Sample Input 2 :
2
3
2 1 3
6
6 5 4 3 2 1
Sample Output 2 :
1
5
Hint

You need to find the longest subsequence in which each term is one greater than the previous term.

Approaches (1)
Hash-map

There is a big observation that we need to preserve the order of some terms, and we can rearrange all other terms, the optimal rearrangement will result in finally sorting the array so we don’t have to take that into account while calculating the answer.

 

As our answer directly depends on the terms that we have to preserve (these terms will not be rearranged), there is another clever observation that these terms should be increasing and should be one unit greater than the previous term. This is because after rearranging all other terms in between, then these preserved terms will come adjacent to each other, and according to the task we had to sort the array in increasing order of the roll numbers. 

 

To do this, we simply need to find the longest subsequence that has the current term one unit greater than the previous one, there are multiple ways to do this, one of the easiest ways to tackle it is by using a hash-map. We can store the maximum length of the subsequence ending with ARR[i] in the hash-map, later when we encounter the ARR[i] + 1 term, we can use the previously stored information to build our answer further.

 

The steps are as follows :

  1. Initialize a hash-map ‘lastTermOfSubseq’.
  2. Declare a variable ‘maxSubseq’ and initialize it to 1, this is because in the worst case we will have to rearrange at most N - 1 terms (as we can always preserve at least one term).
  3. Run a FOR loop for variable ‘i’, to iterate the input array.
    • In each iteration search if ARR[i] - 1 already exists in the hash-map, if it exists then set the value corresponding to ARR[i] in the hash-map equal to lastTermOfSubseq[ARR[i] - 1] + 1. Also update the value of ‘maxSubseq’.
    • If there is no value corresponding to ARR[i] - 1 in the hash-map then, insert the value 1 corresponding to it as this element will be the first term of the subsequence if it is used in the terms to be preserved.
  4. Finally, return the value of N - maxSubseq, as these we will be all the terms that are not preserved and have to be rearranged.
Time Complexity

O( N ), where N denotes the number of students.

 

We iterate through the array of size equal to N, we perform insertion operations in a hash-map which take constant ~O(1) time on average.

Hence the time complexity is O( N ).

Space Complexity

O( N ), where N denotes the number of students.

 

Extra space is used to build the hash-map, there will be ~N terms in the hash-map.

Hence the space complexity is O( N ).

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