Count smaller people on right side

Easy

0/40

Average time to solve is 10m

Contributed by

6 upvotes

Asked in company

Problem statement

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].

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

Sample Output 1:

2 1 1 0
2 0 0

Explanation for Input 1:

For test case 1: Refer the above explanation

For test case 2: 
For the first person with height 5, the people on the right side with a height smaller than 5 are 2nd and 3rd. So for the first person, the count is 2.
For the second person with height 3, there are no people with a height smaller than 3. So for the second person, the count is 0.
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].

Sample Input 2:

Sample Output 2:

4 3 2 1 0
0 0 0

Hint 1

Hint 2

The very first approach is to count for each person independently using a for loop.

Approaches (2)

Approach 1

Approach 2

Brute Force

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.

Time Complexity

O(N * N), where ‘N’ is the number of people.

In the worst case, we run two nested loops of size ‘N’.

Space Complexity

O(1).

In worst case, we are taking constant space.

(100% EXP penalty)

Count smaller people on right side

Console