Count of Smaller Elements

Posted: 1 Apr, 2021
Difficulty: Hard

PROBLEM STATEMENT

Try Problem

Given an array of size 'N' return the count array such that COUNT[i] equals the number of element which are smaller than ARR[ i ] on its the right side.

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.
Try Problem