# Find maximal difference between two consecutive numbers

You are given $$n$$ real (unsorted) numbers $$π₯_1,π₯_2,...,x_n$$. We want to compute the maximal difference between two consecutive numbers in sorted order. Explain how to do it in $$π(π)$$ time when you are allowed to use additions, subtractions, multiplications, divisions and βfloorβ function. Notice that sorting immediately leads to $$π(π logπ)$$ time.

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}$$.