Count Smaller or Equal elements in array

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
73 upvotes
Asked in companies
OlaMathworksIncedo Inc.

Problem statement

You are given two arrays of integers. Let's call the first array A and the second array B. A finds the number of elements in array B that are smaller than or equal to that element for every array element.

For example: 
A = [2, 3, 0] , B = [5, 1]

For the first index, A[0] = 2
In array B only 1 is less than 2. Therefore the answer for the first index is 1.

For the second index, A[1] = 3
In array B only 1 is less than 3. Therefore the answer for the second index is also 1.

For the third index, A[2] = 0
Both the elements of array B are greater than 0. 
Therefore the answer for the third index is 0.

Hence, the final answer is [1,1,0] in this case.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of input contains an integer ‘T’ denoting the number of test cases.
Then the test case follows.

The first line of each test case contains an integer ‘N’ denoting the number of elements in the array A. 

The second line of each test case contains ‘N’ space-separated integers denoting the elements of array A.

The third line of each test case contains an integer ‘M’ denoting the number of elements in array B. 

The second line of each test case contains ‘M' space-separated integers denoting the elements of array B.
Output Format: 
For each test case, print N space-separated integers represent the number of elements in array B that are smaller than the corresponding element in array A.
Note: 
You are not required to print the expected output, it has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 10
1 <= N,M <= 10^4
-10^9 <= A[i] , B[i] <= 10^9

Time limit: 1 second
Sample Input 1:
1
5
5 4 3 2 1
2
3 4
Sample Output 1:
2 2 1 0 0
Explanation of Sample Input 1 :
For the first index, A[0] = 5
Both the elements of Array B are less than 5. Therefore the answer for the first index is 2.

For the second index, A[1] = 4
In array B, one element is smaller than 4 and one element is equal to 4. Therefore the answer for the second index is also 2.

For the third index, A[2] = 3
In array B only one element is equal to 3. Therefore the answer for the third index is 1.

For the fourth index, A[3] = 2
Both the elements of Array B are greater than 2. Therefore the answer for the fourth index is 0.

For the fifth index, A[4] = 1
Both the elements of Array B are greater than 1. Therefore the answer for the last index is 0.

Hence, the final answer is [2, 2, 1, 0, 0] in this case.
Sample Input 2:
1
4
-2 1 3 0
4
-1 0 2 1
Sample Output 2:
 0 3 4 2
Hint

Try to traverse array B for every element of array A and calculate the answer.

Approaches (2)
Brute Force Approach

The idea is to iterate through array B for every element of array A and count the number of elements smaller than or equal to the current element of array A.

 

Let arr be the array of elements in which we will store the answers for each element.

 

We will run a loop from 0 to N - 1 for every element of array A and initialize the answer(arr[i]) for it as 0. Then we will traverse array B for that we will run a loop from 0 to M - 1 and increment the value of the answer by 1 if the element of array A is greater than or equal to the current element of array B.

Time Complexity

O(N * M), where ‘N’ denotes the number of elements of array A and 'M' denotes the number of elements of array B.

 

In the worst case, we need to traverse through the M elements of array B for all the N elements of array A. Hence, the overall time complexity will be O(N * M).

Space Complexity

O(1).

 

In the worst case, only constant extra space is required. We will not consider the space required to store the output array.

Code Solution
(100% EXP penalty)
Count Smaller or Equal elements in array
Full screen
Console