1
$\begingroup$

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.

Please help !

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.