Maximum gap
Given an unsorted array, return the largest difference between two neighbours in its sorted order, in linear time and space. The trick is bucket sort (pigeonhole): the maximum gap can never fall inside a bucket, only between buckets.
No answer yet. Write the first one; the best answer gets endorsed.