Count of Smaller Elements

Posted: 1 Apr, 2021
Difficulty: Hard

PROBLEM STATEMENT

For Example : ARR = [4,2,1,5] the count array corresponding to the given array is :-.

The Number of elements smaller than 4 on its right side is 2.
The Number of elements smaller than 2 on its right side is 1.
The Number of elements smaller than 1 on its right side is 0.
The Number of elements smaller than 5 on its right side is 0.
Hence the count array is [2,1,0,0]
Input Format :
The first line of input contains an integer 'T' denoting the number of test cases.

The first line of the test case contains 'N' denoting the number of elements in an array.

The next line contains 'N' space-separated integers denoting the elements of an array.
Output Format :
For each test case, return the array where ith element stores the count for ith
element in an array.
Note :
You do not need to print anything, it has already been taken
care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= N <= 3000
-10^3 <= arr[i] <= 10^3

Where ‘i’ varies from 1 to ‘N’ where 'N' is the length of the array.

Time Limit: 1 sec Approach 1

The main idea is for every element to count the number of elements less than ARR[i] on its right using a loop.

Algorithm:

• Create an ‘ANSWER’ array of size ‘N’ with an initial value 0.
• Run a loop from ‘i’ = 0 to ‘N’. Inside this run another loop from ‘j’ = ‘i+1’ to ‘N’. If  ARR[i] > ARR[j] then increment the ANSWER[i].
• In the end, return the ‘ANSWER’ array.