Maximum Gap Buckets
Problem
Given a list of integers, return the largest difference between two values that would be adjacent if the list were sorted. Return 0 when fewer than two distinct values exist. Aim for a solution that does not sort the values.
Examples
Input: nums = [3, 6, 9, 1]
Output: 3
Why: sorted the values read 1, 3, 6, 9 and every step is 2 or 3Input: nums = [1, 10000000]
Output: 9999999
Why: two values far apart, so the single gap is the answerInput: nums = [1, 1, 1]
Output: 0
Why: edge case, no two distinct values existHints
0 / 3
Sorting answers it in O(n log n). The target is linear, which means the values must be placed rather than compared.
Spread the values over the range from smallest to largest. If you use n-1 equal buckets, ask how wide a bucket can be and whether the answer can ever fit inside one.
With n values spread over that range, the average step is (max-min)/(n-1), so the largest step is at least that wide and can never be contained inside a bucket of that width. Keep only the smallest and largest value per bucket, then measure every gap from one bucket's maximum to the next non-empty bucket's minimum.
Solution
The pigeonhole principle does the work. With n values spanning hi - lo, some adjacent pair must differ by at least (hi - lo) / (n - 1), so choosing that as the bucket width guarantees the winning gap straddles a bucket boundary. Each bucket then only needs its own minimum and maximum, and the answer is the widest jump from one non-empty bucket's maximum to the next one's minimum. Time is O(n) plus the cost of visiting the buckets in order, space O(n).
def maximum_gap(nums):
if len(nums) < 2:
return 0
lo, hi = min(nums), max(nums)
if lo == hi:
return 0
size = max(1, (hi - lo) // (len(nums) - 1)) # no gap can be smaller
buckets = {}
for n in nums:
b = (n - lo) // size
low, high = buckets.get(b, (n, n))
buckets[b] = (min(low, n), max(high, n)) # only the extremes matter
best, prev = 0, lo
for b in sorted(buckets):
best = max(best, buckets[b][0] - prev) # across a bucket boundary
prev = buckets[b][1]
return best
print(maximum_gap([3, 6, 9, 1])) # -> 3
print(maximum_gap([1, 10000000])) # -> 9999999
print(maximum_gap([1, 1, 1])) # -> 0Stuck on the idea rather than the code? Counting Sort covers it.