Last Updated: 7 Jan, 2021
Count Smaller or Equal elements in array
Moderate
Asked in companies
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.
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
Approaches
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.
The idea is to first sort the array B and use binary search to find the first element with a value greater than the current element.
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. We will first check whether the rightmost(greatest) element of array B is smaller than the current element. If yes, then we will set the answer(arr[i]) to M. Otherwise, we will use binary search in array B to find out the leftmost index in array B having a value greater than A[i]. Let the index of such element be idx. Then we will set arr[i] as j because we are using 0-indexing.
Steps:
- Sort array B in non-decreasing order.
- Traverse each index i from 0 to N - 1 of array A, and do:
- Find the leftmost index in array B for which A[i] > B[j]. Let the index be idx. Set arr[i] to idx.
- If no such index exists then set arr[i] to M ( This is the case when all the elements of array B are smaller than the element of array B).
- Return arr as the final answer.
To implement a binary search, we will use the upper bound function. The Upper bound function returns an iterator to the first index in an array having a value greater than the desired value. It will return an iterator the rightmost element if no such value exists in the array.
Similar problems