632. The Closest Values in Two Sorted Lists
Two non-decreasing lists are given. Choose one value from each and make the absolute difference between them as SMALL as possible.
Print that smallest difference.
1 2 3 11 15 and 8 19 23 127 235 -> 3 from 11 and 8
1 2 3 and 4 5 6 -> 1 from 3 and 4
0 0 and 0 -> 0
## Both pointers move forward
i = 0, j = 0, best = infinity
while i < n and j < m:
best = min(best, abs(a[i] - b[j]))
if a[i] < b[j]: i += 1
else: j += 1
Every step records the current pair and then advances the pointer at the SMALLER value.
## Why advancing the smaller one is right
Suppose a[i] < b[j]. Any pair using a[i] with a LATER value of b has a difference at
least as large as the current one, because b is non-decreasing and every later b is even
further above a[i].
And b[j] has not been ruled out at all; it may still pair well with a later a. So it is
a[i] that is finished, not b[j].
Getting this backwards, advancing the larger one, is the natural mistake and it walks away from the answer instead of towards it.
## Why a difference of zero can stop early
Nothing is smaller than 0, so a solution may return immediately on an exact match. The reference solutions do not bother, because the loop is already linear, but it is a legitimate shortcut.
## Compare with the converging sweeps
Problems 605 and 629 move pointers from OPPOSITE ends, because they are chasing a target sum and the two directions push the sum in opposite ways.
Here both pointers move forward, because the two lists are being walked in step and the question is about proximity, not about a total. Which layout a problem wants follows from what moving a pointer does to the quantity being measured.
## Overflow
Two values near 10^9 of opposite sign differ by about 2 * 10^9. Check that against the
limit rather than assuming: a signed 32 bit integer holds up to 2147483647, so
2000000000 FITS, with about seven percent to spare. This problem has no overflow.
Widen the value range by a single order of magnitude and the same subtraction needs 64 bits, which is the point: the bound is a property of the constraints, so it has to be recomputed whenever they move rather than remembered from a similar-looking problem.
## Cost
Time O(n + m). Space O(1).
Constraints - `1 ≤ n, m ≤ 200000` - `-10^9 ≤ each value ≤ 10^9` - both lists are non-decreasing
Input
The first line contains two integers n and m.
The second line contains n integers in non-decreasing order.
The third line contains m integers in non-decreasing order.
Output
Print one integer, the smallest absolute difference between a value of the first list and a value of the second.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.