Do any two trades fall within t nanoseconds

Question

You suspect a burst of near-simultaneous trades. Given unsorted trade timestamps and a tolerance t, decide whether any two timestamps are within t of each other.

timestamps = [100, 250, 130], t = 40
-> True          # 100 and 130 are 30 apart

Return True if some pair of timestamps differs by at most t, else False. Aim for $O(n \log n)$ .

Accepted Answer

If any pair is within t, the closest such pair must be adjacent after sorting, sorting cannot separate two values that are close by placing something between them without that something also being close to at least one of them. So sort, then check consecutive differences; if the smallest one is at most t, a qualifying pair exists. Tracing [100, 250, 130] with t = 40: sorted it is [100, 130, 250]. The gap 130 - 100 = 30 is within 40, so the answer is True. Time O(n \log n) for the sort, space O(n) for the sorted copy (or O(1) if you sort in place). Edge cases: fewer than two timestamps returns…

Do any two trades fall within t nanoseconds

Your answer

More Coding questions