Loading page…
Practice problem · easy
An online store logs the time of day of every order as the number of seconds since midnight. Support wants the two orders that came closest together on the clock, because a tight pair is often a duplicate.
The clock repeats every day, which has 86,400 seconds. An order at 86,399 and one at 0 are only 1 second apart, going past midnight.
Write smallest_gap(times).
times[i] is the time of order i, in seconds since midnight.Input: times = [64800, 300, 43200, 64810]
Output: 10Sort the times, then look at the gap between each neighbour pair. The last pair to check is the last time round midnight to the first.
| Pair | Gap |
|---|---|
| 300 and 43200 | 42900 |
| 43200 and 64800 | 21600 |
| 64800 and 64810 | 10 |
| 64810 round midnight to 300 | 21890 |
The smallest gap is 10.
Input: times = [86399, 1]
Output: 2Going forward from 86399, midnight is 1 second away and then second 1 is 1 more, so the gap is 2. The long way round is 86,398.
Input: times = [5000, 5000, 40000]
Output: 0Two orders in the same second are 0 apart.
2 ≤ times.length ≤ 100,000 (orders)0 ≤ times[i] ≤ 86,399 (seconds since midnight)Checking every pair costs about n × n / 2, which is 5 × 10^9 at n = 100,000. Sorting costs about n log n. A day has only 86,400 distinct seconds, so a list longer than that must contain a repeat, and its answer is 0.
smallest_gap · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.