Editor

Closest Readings From Two Sensors

#626 · Two pointers · Intermediate · Fast enough · 85 XP · about 18 min

Two sensors in a lab each logged a long list of readings, as whole numbers, in no particular order. To check that the sensors agree, you want to know how close a reading of the first sensor ever comes to a reading of the second.

Write closest_gap(first, second) that returns the smallest value of abs(a - b) where a is a reading in first and b is a reading in second.

Examples

closest_gap([1, 15, 9], [20, 12, 30])  # returns 3
closest_gap([500, -20], [-25, 700])    # returns 5
closest_gap([7, 3], [3])               # returns 0

In the first example the closest readings are 15 and 12.

Constraints

  • 1 <= len(first) <= 100,000 and 1 <= len(second) <= 100,000
  • Readings are whole numbers from -1,000,000,000 to 1,000,000,000.

Time limit

Each test must finish within 10 seconds, and the hidden tests have 100,000 readings in each list.

Fastest solvers

Leaderboard

First solves only, ranked by stars and then time.