Given two unsorted arrays A, B. For each element in A count elements less than or equal to it in array B

Problem: Given two unsorted arrays A, B. They can contain duplicates. For each element in A count elements less than or equal to it in array B.

For example:

Input: arr1[] = {1, 2, 3, 4, 7, 9}
       arr2[] = {0, 1, 2, 1, 1, 4}

Output: 4 5 5 6 6 6

Total elements less than or equal to 1 in arr2 are 4 (0, 1, 1, 1). Similarly
for other elements of arr1.

Method 1: The naive approach is to use two nested loops. Outer loop is used to select element of arr1 one by one. Inner loop counts the elements less than or equal to the corresponding element of arr1 in arr2.

Time Complexity: O(m*n), n = sizeof(arr1) and m = sizeof(arr2)

Method 2: An efficient method is to sort the arr2, then use binary search to get the index of the element that is equal to or less than the corresponding element of arr1 in arr2. Following is the implementation of the approach.

#include <bits/stdc++.h>
using namespace std;

/* function to print the requered result */
void totNum(int arr1[], int arr2[], int n, int m)
{
    /* sort array2 */
    sort(arr2, arr2 + m);

    for( int i = 0; i < n; i++)
    {
        /* getting the postion of the element less than or equal
           to arr1[i] */
        int pos = upper_bound(arr2, arr2 + n, arr1[i]) - arr2;
        cout<<pos<<" ";
    }
}

/* driver function */
int main()
{
    int arr1[] = {1, 2, 3, 4, 7, 9};
    int arr2[] = {0, 1, 2, 1, 1, 4};
    int n = sizeof(arr1)/sizeof(arr1[0]);
    int m = sizeof(arr2)/sizeof(arr2[0]);

    totNum(arr1, arr2, n, m);
    cout<<"\n";
 
    return 0;
}

Output:

4 5 5 6 6 6

Time Complexity: O(nlogn)