Maximum Gap
Solve and submit on LeetCode to build your LeetCode profile. Use the hints here when you need guidance.
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
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)
