Maximum Gap

Hard· bucket sort· pigeonhole

Problem

Return the largest difference between two neighbouring values once the array is sorted, or 0 if it has fewer than two elements. The algorithm must run in linear time and linear space, so a comparison sort is not allowed.

Examples

Input: nums = [3,6,9,1]

Output: 3

Sorted it is [1,3,6,9]; the gaps are 2, 3, 3.

Input: nums = [10]

Output: 0

Constraints

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^9

Hints & approach

Hint 1

Radix sort is linear for bounded integers and would work.

Hint 2

By pigeonhole, the maximum gap is at least (max - min) / (n - 1).

Hint 3

Use buckets of that width; the answer never lies inside a bucket, only between buckets.

Approachtry the hints first

Find min and max. Set bucket width w = max(1, (max - min) / (n - 1)) and create about (max - min) / w + 1 buckets, each tracking only its minimum and maximum. Place every value in bucket (x - min) / w. Because the largest gap is at least w, it can never be between two values in the same bucket. Scan the non-empty buckets in order and take the largest difference between a bucket's minimum and the previous non-empty bucket's maximum.

Time O(n) · Space O(n)

← PreviousLargest Number DoneBack to Sorting algorithms