See the original problem on HackerRank.
Given two unsorted arrays arr1 and arr2  possibly containing duplicates  for each element in arr1 print the number of elements less than or equal to it in array arr2.
Input Format
The first line contains an integer N.
Two lines follow:
the first array: N spaceseparated elements
the second array: N spaceseparated elements
Constraints
N and M are at most 100’000 Each array element is at least 1 and at most 100’000.
Output Format
For each element in the first array, print a line containing the number of elements in the second array that are less or equal. The last line is always empty.
Example
Input:
1 2 3 
6 10 5 80 1 7 20 11 21 6 1 0 1 
Output:
1 2 3 4 5 6 
4 3 6 3 4 5 
Explanation:
From the first array:
 10 is greater or equal than {6, 1, 0, 1}, so we print 4;
 5 is greater or equal than {1, 0, 1}, so we print 3;
 80 is greater or equal than all the numbers of the second array, so we print 6;
 1 is greater or equal than {1, 0, 1}, so we print 3;
 7 is greater or equal than {6, 1, 0, 1}, so we print 4;
 20 is greater or equal than {11, 6, 1, 0, 1}, so we print 5;
Solutions
One solution is based on sorting + binary search. Here it is in C++:


Another one is based on prefix sum of the frequency array:


Prefix sum solution in Javascript by Simone Busoli:


The tradeoff here is on the length of the second sequence compared to the domain size:
 if the second sequence is small, saving time with prefix sum is probably useless.
 however, if the second sequence is huge, sort and binary search can be heavy.