Number of Subordinates

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 space-separated elements

the second array: N space-separated 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++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
int N; cin >> N;
vector<int> v1(N), v2(N);
copy_n(istream_iterator<int>(cin), N, begin(v1));
copy_n(istream_iterator<int>(cin), N, begin(v2));
  sort(begin(v2), end(v2));
for (auto i : v1)
{
	auto it = upper_bound(begin(v2), end(v2), i);
	cout << distance(begin(v2), it) << "\n";
}

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
int N; cin >> N;
vector<int> v1(N), v2(N);
copy_n(istream_iterator<int>(cin), N, begin(v1));
copy_n(istream_iterator<int>(cin), N, begin(v2));
  array<int, 100'001> freq{};
for (auto i : v2)
	freq[i]++;
partial_sum(begin(freq), end(freq), begin(freq));

for (auto i : v1)
	cout << freq[i] << "\n";

Prefix sum solution in Javascript by Simone Busoli:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
function processData(input) 
{
    const [,f,s] = input.split('\n').map(l => l.trim().split(' ').map(Number))
    
    s.sort((a,b) => a-b)
    
    const [,pf] = s.reduce(([count, arr], c) => {
      arr[c] = ++count
      return [count, arr]
    }, [0, []])
    
    let lastValue = 0;
    
    for(let i = 0; i < pf.length; i++) {
      if(pf[i]) lastValue = pf[i] 
      else pf[i] = lastValue
    }
  
    f.forEach(fe => console.log(fe < pf.length ? pf[fe] : pf[pf.length - 1]))
}

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.
We've worked on this challenge in these gyms: modena 
comments powered by Disqus