Smaller Elements Count Problem Statement

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

Input:

Input Format:

The first line of input contains an integer 'T' denoting the number of test cases.
The first line of each test case contains 'N' denoting the number of elements in the array.
The next line contains 'N' space-separated integers denoting the elements of the array.

Output:

Output Format:

For each test case, return the array where the i-th element stores the count for the i-th
element in the array.

Example:

Input:

ARR = [4,2,1,5]

Output:

[2,1,0,0]

Explanation:

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

Constraints:

1

Question

Smaller Elements Count Problem Statement

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

Input:

Input Format:

The first line of input contains an integer 'T' denoting the number of test cases.
The first line of each test case contains 'N' denoting the number of elements in the array.
The next line contains 'N' space-separated integers denoting the elements of the array.

Output:

Output Format:

For each test case, return the array where the i-th element stores the count for the i-th 
element in the array.

Example:

Input:

ARR = [4,2,1,5]

Output:

[2,1,0,0]

Explanation:

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

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

Accepted Answer

Return an array where each element represents the count of smaller elements on its right side in the given array.

Iterate through the array from right to left and maintain a sorted list of elements encountered so far.
For each element, find its index in the sorted list to determine the count of smaller elements on its right side.
Use binary search or segment trees for efficient searching and updating of the sorted list.

Smaller Elements Count Problem Statement

Input:

Input Format:

Output:

Output Format:

Example:

Input:

Output:

Explanation:

Constraints:

SPRINKLR Full Stack Engineer interview questions & answers

Popular interview questions of Full Stack Engineer