On a hike, your camera logs the time of each photo and a separate GPS watch logs the time of each position fix, both in seconds and both sorted in non-decreasing order. A photo and a fix "match" when their times differ by at most d seconds.
Write count_matches(photos: list[int], fixes: list[int], d: int) -> int that returns the number of (photo, fix) pairs that match, i.e. pairs of indexes (i, j) with abs(photos[i] - fixes[j]) <= d.
count_matches([10, 20, 30], [12, 18, 40], 3) # 2 (10,12) and (20,18)
count_matches([5, 5], [5, 7], 2) # 4 every photo matches every fix
count_matches([], [1, 2], 10) # 0
0 <= len(photos), len(fixes) <= 10^5; times are in[0, 10^9]and may repeat;0 <= d <= 10^9.- Checking every pair is O(n·m), 10^10 pairs at the maximum size; the tests include a case that size. Aim for O(n + m), and don't use
bisect: the point is to walk the pointers.
Show hint
as the photo time rises, the window of matching fixes, [photo - d, photo + d], only moves right; keep two indexes into fixes, lo (first fix >= photo - d) and hi (first fix > photo + d), advance each with a while loop, and add hi - lo for each photo.