Array "maximum difference" algorithm that runs in O(n)?

Question

Given an array of N integers, sort the array, and find the 2 consecutive numbers in the sorted array with the maximum difference.

Example – on input [1,7,3,2] output 4 (the sorted array is [1,2,3,7], and the maximum difference is 7-3=4).

Algorithm A runs in O(NlogN) time.

I need to find an algorithm identical in function to algorithm A, that runs in O(N) time.

Answer 1

Let the array be X and let n = length(X). Put each element x in bucket number floor((x - min(X)) * (n - 1) / (max(X) - min(X))). The width of each bucket is (max(X) - min(X))/(n - 1) and the maximum adjacent difference is at least that much, so the numbers in question wind up in different buckets. Now all we have to do is consider the pairs where one is the max in bucket i and the other is the min in bucket j where i < j and all buckets k in (i, j) are empty. This is linear time.

Proof that we really need floor: let the function be f(X). If we could compute f(X) in linear time, then surely we could decide in linear time whether

0 < f(X) ≤ (max(X) - min(X))/(length(X) - 1),

i.e., whether the elements of X are evenly spaced and not all identical. Let this predicate be P(X). The support of P has factorial(length(X)) connected components, so the usual Ω(n log n) lower bounds for algebraic models of computation apply.

Answer 2

Execute a Counting Sort and then scan the result for the largest difference.

Because of the consecutive number requirement, at first glance it seems like any solution will require sorting, and this means at best O(n log n) unless your number range is sufficiently constrained for a Counting Sort. But if it is, you win with O(n).