Determine the minimum $a$ and maximum $b$ in a first pass.

Create $n+1$ buckets, each of width $frac{b-a}{n+1}$, with the first beginning at $a$. We have $n+1$ buckets and only $n$ points, so by the pigeonhole principle, there must be at least one empty bucket. Since we know that the first and last buckets contain at least one point, we know furthermore that there must be an empty bucket with a nonempty bucket somewhere to its left and another nonempty bucket somewhere to its right, implying that the solution must be at least $frac{b-a}{n+1}$.

This means that **no two points within the same bucket can provide the solution**, since they must be strictly less than $frac{b-a}{n+1}$ apart from each other. So, any solution will consist of a pair of points from *different* buckets.

A valid solution must consist of the rightmost point from some bucket $i$ and the leftmost point from some bucket $j > i$ with all buckets in between (which may be no buckets at all, when $j=i+1$) empty. So it is sufficient to know, for each bucket, its leftmost and rightmost points.

To compute these, iterate through all the points again, updating the leftmost and rightmost positions of the current point’s bucket whenever necessary. (For the first point in a bucket, both of these positions will need to be updated.) A point’s bucket can be computed by subtracting $a$ and dividing by $frac{b-a}{n+1}$.

Finally, iterate through all the buckets, keeping track of the rightmost point in the last nonempty bucket seen, and comparing it with the leftmost point in the current bucket: Update the maximum whenever this exceeds the current maximum.