Rearrange the positions by height.

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
1 upvote
Asked in company
Apple

Problem statement

You are given an 'N' x 2 matrix ‘ATTRIBUTES’ of some people standing in random order where ‘ATTRIBUTES[ i ][ 0 ]’ denotes the height of the ‘ i-th ‘ person and ‘ATTRIBUTES[ i ][ 1 ]’ denotes the number of people that are in front of the ‘ i-th’ person having a height equal to or more than the height of the i-th person, i.e. ‘ATTRIBUTES[ i ][ 0 ]’ .

You need to rearrange the list such that every person is in its correct position, i.e., exactly ATTRIBUTES[ i ][ 1 ] number of people should be in front of ‘ i-th’ person with height more than ATTRIBUTES[ i ][ 0 ].

For Example: 
If the given list is [ [ 4, 2], [ 6, 1 ], [ 10, 0 ], [ 1, 1] ].
The correct order should be [ [ 10, 0 ], [ 1, 1 ],  [

6, 1 ], [ 4, 2 ] ].

A person with a height of ‘10’ has ‘0’ persons in front with a height more than ‘10’. So this person should be in the first place.
A person with a height of ‘1’ has ‘1’ person with a height of more than 1, so it is placed after [10,0].
A person with a height of ‘6’ has ‘1’ person in front with a height more than ‘ 6 ’.So this should be at the third position as 10 > 6.
A person with a height of ‘ 4 ’ has ‘2’ persons in front with a height more than ‘ 4 ‘.So this should be at the last position as 10 > 4 and 6 > 4.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains ‘T’, denoting the number of test cases to be performed.

The first line of each test case contains an integer ‘N’ indicating the number of persons.

Then 'N' lines follow. Each line represents the elements of the 'N' x 2 matrix where each row denotes the two attributes value.
Output Format: 
For each test case, return the rearranged 'N' x 2 matrices having all the persons at their correct position.
Note: 
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints 
1 <= T <= 10
1 <= N <= 10^3
1 <= ATTRIBUTES[ i ][ 0 ] <= 10^5
1 <= ATTRIBUTES[ i ][ 1 ]  <= N

Time Limit: 1 sec
Sample Input 1:
2
4
24 1
13 2
12 1
25 0   
2
8 0
4 0
Sample Output 1:
25 0
12 1
24 1
13 2
4 0
8 0
Explanation Of Sample Input 1:
Test Case 1: The correct order of this case is [ [ 25, 0], [ 12, 1 ], [ 24, 1 ], [ 13, 2 ] ].
A person with a height ‘25’ has 0 number of people in front with more height, So it is placed at the first position.
A person with a height of 12 has exactly 1 person in front with more height. As 25 > 12 So it is placed at the second position.
A person with a height of 24 also has only 1 person in front with greater height. As 25 > 24 and 12 < 24. 
The last person has a height of ‘13’, which is less than 24 and 25. Therefore this person has 2 people in front with more height.

Test Case 2: There are two people, and no one has persons in front with more height.Therefore correct positions will be [ [ 4, 0 ], [ 8, 0 ] ].
Sample Input 2:
2
1
7 0
3
16 1
21 0
11 2
Sample Output 2:
7 0
21 0
16 1
11 2
Hint

Try to fix the position of the shortest person.

Approaches (2)
Brute force Approach
  • The basic idea is that we will find every person’s correct position one by one and place the person in that position.
  • We will first sort the given array according to the persons’ height, and if two persons have the same height, we will sort them according to their second attribute value.
  • After sorting, if we are iterating in ascending order, it is sure that all future persons will have height either equal to or more than the current person’s height.
  • We will place the persons in the correct position by keeping the above point in mind.
  • For example, if the list is [ 4,2 ] [ 2,0 ], [ 5,1] , [10,0]] . After sorting list, it’s- [ [2,0] , [ 4,2 ] [ 5,1 ], [ 10,0] ].
  • Now person having a height of 2,  will be placed in the first position.
  • For the second person with a height of ‘4’, if we place it at the second position, no person will have a height more than ‘4’ in front of it as 2 < 4. So we will skip the second position, which the future persons will occupy with a height of more than ‘4’.
  • If we place it at the third position, then there will be only one person with a height of more than ‘4’ in front of it. So we will skip this position too.
  • So we will place this person in the fourth position.
  • Place all the persons as the above method.

 

Algorithm:

 

  • Maintain a 2-D array 'ANS' (initialized all values to -1) to store the rearranged elements.
  • Sort the elements according to the height of persons. In case of same height sort according to second attribute value.
  • Take a variable ‘ COUNT ’ that will store the second attribute value of every person.
  • Iterate for every person - i : 0 to N-1
    • Update 'COUNT' as the ATTRIBUTES[ i ][ 1 ].
    • Run a loop j : 0 to N-1 to find the correct position in the 'ANS' array.
      • If COUNT = 0 i.e we got required number of persons in front with height more than height of ‘i-th’ person and ANS [ j ][ 0] = -1 i.e current position is empty.
        • Place the ‘ i- th ‘ person at this ‘ j ‘ position.
      • Else
        • If ANS [ j ][ 0 ] = -1 or ANS [ j ][ 0 ] > ATTRIBUTES [ i ] [ 0 ] - Decrement ‘COUNT’.
  • Return 'ANS'.
Time Complexity

O(N^2), where ‘N’ is the total number of persons.

 

For every person, we are iterating for every position value. Therefore time complexity will be O(N^2).

Space Complexity

O( N ), where ‘N’ is the total number of persons.

 

We are using an extra array ‘ans’ to store the correct sequence of attributes, making the space complexity O( N ).

Code Solution
(100% EXP penalty)
Rearrange the positions by height.
Full screen
Console