Count of Smaller Elements

Hard

0/120

Average time to solve is 45m

Contributed by

27 upvotes

Asked in companies

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]

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

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

Hint 1

Hint 2

Hint 3

For arr[i], count the number of greater elements in (i,N-1]

Approaches (3)

Approach 1

Approach 2

Approach 3

Brute force

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.

Time Complexity

O(N^2) where ‘N’ is the size of the array

Running a nested loop of ‘N’ steps ‘N’ times where ‘N’ is the size of the array. Thus time complexity is O(N^2).

Space Complexity

O(1)

We are using constant space to solve this.

(75% EXP penalty)

(100% EXP penalty)

Count of Smaller Elements

Console