How do you find the largest gap in a vector in O(n) time?

Question

You are given the locations of various cars in the same lane on a highway as doubles to a vector, in no particular order. How can you find the largest gap between neighboring cars in O(n) time?

It seems like a simple solution would be to sort then check, but of course this isn't linear.

Answer 1

Divide the vector in n+1 equally sized buckets. For each such buckets, store the maximum and the minimum value, all other values can be discarded. Because of the pigeonhole principle, at least one of those parts is empty, so the non-minimum/non-maximum values in either parts don't have an influence for the result.

Then, go over the buckets and calculate the distance to the next and the previous non-empty bucket, and take the maximum; this is the final result.

An example with n=5 and values 5,2,20,17,3. Minimum is 2, maximum is 20 => bucket size is (20-2)/5 = 4.

Bucket:   2    6    10    14     18     20
Min/Max:   2-5   -    -     17,17  20,20

Differences: 2-5, 5-17, 17-20. Maximum is 5-17.