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.
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.
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:
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.