Last Updated: 1 Apr, 2021

Count of Smaller Elements

Hard

Asked in companies

Solve now

Problem statement

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

Solve now

Approaches

01 Approach

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.

Solve now

02 Approach

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.

Solve now

03 Approach

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.

Solve now