# 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 0 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 v1(N), v2(N); copy_n(istream_iterator(cin), N, begin(v1)); copy_n(istream_iterator(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 solition, sort both, remember indexes.

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55  fn main() { use std::io::BufRead; let stdin = std::io::stdin(); /* Skip first line, parse other lines, splitting by spaces */ let mut lines: Vec> = stdin .lock() .lines() .skip(1) .map(|line| { line.unwrap() .split_whitespace() .flat_map(str::parse) .collect() }) .collect(); let mut arr2 = lines.pop().unwrap(); /* Add indexes */ let mut arr1: Vec<(usize, u32)> = lines .pop() .unwrap() .iter() .cloned() .enumerate() .collect(); /* Descending sort by value, keep the index */ arr1.sort_by(|(_, x), (_, y)| y.cmp(x)); arr2.sort_by(|x, y| y.cmp(x)); /* Remember how many elements to skip */ let mut to_skip = 0; let mut result = Vec::new(); for &(i, x) in arr1.iter() { /* Find the first less or equal than x. All following will also * be less or equal than x, because they are sorted descending */ if let Some(m) = arr2.iter().skip(to_skip).position(|&y| x >= y) { result.push((i, (arr1.len() - m - to_skip) as u32)); to_skip = m; } else { result.push((i, 0)); } } result.sort(); for (_, r) in result { println!("{}", r); } } 

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 v1(N), v2(N); copy_n(istream_iterator(cin), N, begin(v1)); copy_n(istream_iterator(cin), N, begin(v2)); array 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  padua  milan