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 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<Vec<u32>> = 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<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