Last Updated: 30 Dec, 2020
Count smaller people on right side
Easy
Asked in company
You are given the height of N people standing in a queue in an array 'HEIGHT'. For each person, you need to calculate the number of people on the right side of the given person who is smaller in height.
For example:
For N = 4 and height[] = [6, 3, 7, 2]
For the first person with a height of 6, the people on the right side with a height smaller than 6 are the 2nd and 4th person. So for the first person, the count is 2.
For the second person with height 3, the person on the right side with a height smaller than 3 is the 4th person. So for the second person, the count is 1.
For the third person with a height of 7, the person on the right side with a height smaller than 7 is the 4th person. So for the third person, the count is 1.
For the last person, the count is 0 as there are no people left on the right-hand side. So for the last person, the count is 0.
So the Count[] is [2, 1, 0, 0].
Input format:
The first line contains an integer 'T' denoting the number of test cases or queries to be run.
The first line of each test case or query contains a single integers 'N' denoting the number of people.
The second line of each test case contains N single space-separated integers denoting heights of N people respectively.
Output Format:
For each test case, print a single line containing N single space-separated integers denoting the count of people on the right-hand side with a height smaller than the given person.
The output of each test case will be printed 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 <= 5
1 <= N <= 10 ^ 5
0 <= HEIGHT[i] <= 10 ^ 9
Where 'T' is the number of test cases, 'N' is the length of the array and 'HEIGHT[i]' is the height of a person at index i.
Time limit: 1 sec
Approaches
- The idea is to use two loops.
- The first loop picks each person one by one from left to right.
- The second loop iterates through all people on the right side of the picked person and counts the people with smaller height.
- Update your Count[] array for each person.
- The idea is to use merge sort.
- By modifying the merging array part of merge sort, we can calculate the required ans.
- During merging of two halves, when the higher index element is less than the lower index element, it represents that the higher index element is smaller than all the elements after that lower index because the left part is already sorted. Hence add up to all the elements after the lower index element for the required count.
- For example :
- Suppose our left half is [ 2, 5, 6, 8 ] and our right half is [ 3, 4, 7]. Now if any value at higher index (i.e. in the right half) say 3 is smaller than any value at lower index (i.e. in the left half) say 5 then 3 is also smaller than all elements after 5 i.e from 6 and 8. And so it adds up to all the elements after 5.
- We will use the function MergeCount() to count the ans for a particular range of people. Initially, our range is 0 to n-1.
- The MergeCount() function will perform three operation.
- Recursively call MergeCount() for the left half.
- Recursively call MergeCount() for the right half.
- Call another helper function Merge() to merge both the halves.
Similar problems