Find the max gap among \(n\) integers, in linear time and space.

The problem is stated in an ambiguous way that could be interpreted as asking for the largest difference between successive elements of the unsorted sequence, but regardless of what the original questioner wanted, what I want is the largest gap in the sequence formed by sorting the input.

Of course, since max gap has an \(n\log n\) lower bound in certain real-number computation models, one has to use the fact that the inputs are integers and assume a reasonable set of binary integer operations. On the other hand, I haven't said how much precision the inputs have, which makes the obvious linear-time integer sorting solution problematic. But the precision doesn't matter! After subtracting the minimum value from all the inputs, and determining the highest nonzero bit of any remaining value, to normalize the range, one can bucket-sort the inputs by their first \(\log^2 n + O(1)\) bits, and the max gap will be between the max of some bucket and the min of the next nonempty bucket.




Comments:

None:
2007-06-19T05:58:25Z
... and of course this is known at least since Gonzalez 1975 according to Preparata and Shamos "Computational Geometry" page 261. Still, a real gem.
11011110:
2007-06-19T06:08:33Z
I didn't think this was likely to be at all new, but hadn't taken the effort to track down the proper reference — thanks for doing so!