Quakes close in time
Seismologists look for shocks that happened close to each other in time: that is how aftershocks and earthquake swarms are found. Given n moments of time in seconds and a number T. How many pairs of events are at most T seconds apart? Pairs are unordered: a pair of events is counted once.
The second and third tests are all 19,073 earthquakes of magnitude 5 and up in 2015–2025 from the USGS catalogue, with time in seconds from the start of 2015, and a window of an hour and of a day.
Before writing code, estimate: how many steps will trying all pairs take at n = 2·10⁵, and how many seconds that is.
Input
The first line holds n and T (1 ≤ n ≤ 2·10⁵, 0 ≤ T ≤ 10⁹). The second holds n integers t1, …, tn (0 ≤ ti ≤ 10⁹) in arbitrary order; moments may coincide.
Output
One number: the number of pairs i < j with |ti − tj| ≤ T.
Examples
Example 1
6 3600 7200 0 3600 100000 3601 7200
7
Limits
- Time · Python
- 3000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 8 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
At n = 2·10⁵ there are about 2·10¹⁰ pairs. Even if checking one pair costs a nanosecond, that is twenty seconds. So the pairs have to be counted without trying them. What changes if the moments are put in order?
2The idea
Sort the moments. For event i, all later events at most T away from it come in a row right after it, up to the first one that is already farther. If the end of this block j is known, event i gives j − i − 1 pairs. And when i moves to the right, the end of the block can only move to the right: two pointers.
3Walkthrough
Sorting is O(n log n), about 3.5·10⁶ comparisons. The pointer j moves at most n times over the whole pass, so the second stage is linear. Instead of the second pointer the end of the block can be found for each i by binary search, also O(n log n).
The answer can be large: if all events are in one window, there are n(n − 1)/2 ≈ 2·10¹⁰ pairs, while a 32-bit integer holds only 2.1·10⁹. In Go int is 64-bit, and Python integers do not overflow, but in other languages it is easy to go wrong here.
It is interesting to look at trying all pairs. On the real catalogue that is 1.8·10⁸ checks: Go copes in a fraction of a second, while Python takes seconds and does not fit the limit. On 2·10⁵ events trying pairs passes nowhere: Go needs several seconds, Python minutes. That is exactly the estimate worth making before writing the code.
3+Solution
4Complexity
O(n log n) for sorting and O(n) for counting.
5Common mistakes
- Trying all pairs. Correct, but 2·10¹⁰ checks fit in no limit.
- Forgetting to sort. In the real catalogue the events are already in order of time, but in the other tests they are not.
- Coinciding moments. Pairs with ti = tj count too. In the seventh test the window is zero, and there are no other pairs.
- A 32-bit counter. In the sixth test the answer is almost 5·10⁹.
Algorithms behind it
the estimate takes seconds in your head
1 problem
SRT
Algorithm
Binary search
Finds the “no → yes” boundary in ordered data in log₂ n checks.
O(log n)
2 problems