1605. The Two Closest Points on a Line
Given n points on a line, print the smallest distance between any two of them.
3 1 4 1 5 -> 0 the two 1s sit on top of each other
10 1 -> 9
1 2 3 4 -> 1
Two points at the same coordinate are distance 0 apart, and that is a legal answer.
## What most people try first
Every pair, which is O(n^2): at n = 2 * 10^5 that is 2 * 10^10 distance
tests.
## Sort, then look only at neighbours
sort the coordinates
answer = the smallest gap between CONSECUTIVE values
That is O(n log n) and it is the whole solution. The one-dimensional case is
easy precisely because sorting puts every candidate pair next to each other.
## Why only neighbours need checking
Suppose the closest pair is x and y with x < y, and some third point z
lies between them. Then z - x is smaller than y - x, so x and z are
closer than x and y, contradicting that x and y were closest.
So no point lies strictly between the closest pair, which is exactly what "consecutive after sorting" means. The argument is short and it is the thing to carry away: the sort does not find the answer, it removes every pair that cannot be the answer.
## Why this problem is in the divide-and-conquer topic
Because of what it becomes in two dimensions. There, sorting by x no longer
makes the closest pair adjacent, and the standard solution splits the points in
half, solves each side, and then checks a STRIP of width d around the dividing
line, where d is the better of the two half-answers. The strip needs at most a
constant number of comparisons per point, which is the part that makes it
O(n log n) rather than O(n^2).
Seeing the one-dimensional case first makes that strip argument readable: the strip is doing in two dimensions what "consecutive after sorting" does in one.
## The boundary
Duplicate coordinates give distance 0, so a solution tracking a strictly positive minimum, or skipping equal values as "the same point", is wrong. Two points at the same place are still two points.
## Overflow
Coordinates reach 10^9 in magnitude, so a distance between opposite extremes
reaches 2 * 10^9. A signed 32 bit integer holds up to 2147483647, so that
FITS, with about seven percent to spare. Nothing here accumulates, so 32 bits is
sufficient throughout.
## Cost
O(n log n), dominated entirely by the sort; the scan afterwards is O(n).
Constraints - `2 ≤ n ≤ 200000` - `-10^9 ≤ each coordinate ≤ 10^9` - coordinates may repeat
Input
The first line contains the integer n.
The second line contains n integers, the coordinates of the points on a line.
Output
Print one integer on its own line: the smallest distance between any two of the points, which is 0 when two points share a coordinate.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.