# Count of Smaller Elements

Posted: 1 Apr, 2021

Difficulty: Hard

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

Approach 2

**The main idea is that we will use the Fenwick tree to store the count of elements and to get the count for elements. To know more about Binary Index Tree refer to this:- (****https://cp-algorithms.com/data_structures/fenwick.html****)**

**Algorithm:**

**Create an answer array of size 'N' with an initial value 0.****Create the update and query function of the Binary Index Tree.****The values in the array are negatives also. Hence we use the coordinate compression technique in such a way that all values are greater than 0 and the range is reduced.****Run a loop from i='N' - 1 to 0 where 'N' is the length of the array. For arr[i] we will use the query function of the Binary Index tree to get the count of values less than arr[i]. This is the answer for ith index. Hence ans[i] equal to the value which we get from the query function.****Now we need to update arr[i] in the Binary Index tree. Hence called the update function of Fenwick Tree with a value equal to 1. (Since we are incrementing the count of arr[i]).****In the end, return the answer array.**

Approach 3

**The key idea is similar to merge sort divide the array into two parts until the base case is reached that is when the size is less than or equal to 1.**

**Algorithm :**

**Create a list ‘ARR1’ such that ‘ARR1[i]’ stores [ARR[i],i].Create an ‘ANS’ list of size of 'N' with default value 0.****Create a recursive function that divides the list ‘ARR1’ into two sorted list by the value.****Create a function merge similar to merge sort one that will merge two sorted list into one.****In the merge function create two indices i and j, i is the index for the first half, and j is an index of the second half. Create a variable count with a value of 0.if ARR1[i][0] greater than ARR1[j][0] then do temp++.Else do ANS[ARR1[i][1] += temp.(Adding the values which are less than ARR1[i][0] corresponding to its index) and then do i++.****After this run a loop until i<mid and do ANS[ARR[i][1]]+=temp(To update the values for remaining elements.****In the end, return ‘ANS’ list.**