Count smaller people on right side

Posted: 30 Dec, 2020
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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
Approach 1
  1. The idea is to use two loops.
  2. The first loop picks each person one by one from left to right.
  3. The second loop iterates through all people on the right side of the picked person and counts the people with smaller height.
  4. Update your Count[] array for each person.
Try Problem