LC 0164 [H] Maximum Gap - ALawliet/algorithms GitHub Wiki

we use buckets and a special formula for the index so that so that we can disregard the values in each bucket against each other

so the candidates are only between adjacent buckets, the min of one and the max of its previous

@dbabichev
for people reading this, maybe this would help understanding how it works: basically we argue that the largest gap can not be smaller than (max-min)/(N-1), so if we make the buckets smaller than this number, any gaps within the same bucket is not the amount we are looking for, so we are safe to look only for the inter-bucket gaps.

so making the buckets smaller doesn't affect the correctness. for safety we might just as well use (max-min)/2N

@theflyinggemini
we want to make sure those two numbers forming the maximum difference fall into separate buckets so that we do not need to worry about the numbers in the same bucket. To achieve this we want the size of each bucket to be less than the maximum difference.

Assuming md denotes the maximum difference, then we have md * (len(nums) - 1) >= b - a, so md >= (b - a) / (len(nums) - 1), since md must be integer, we get md >= math.ceil((b - a) / (len(num) - 1)), thus we make size = math.ceil((b - a) / (len(num) - 1)).

Then by making the number of buckets to be (b - a) // size + 1, it is guaranteed that the final bucket size is less than maximum difference hence those two numbers forming maximum difference will be in separate buckets.

Finally, we find the maximum difference between two adjacent buckets (min value of current bucket and max value of previous bucket) and that will be the answer.

I'd also like to think of it as an average, (hi - lo)/(n - 1) gives the average of each gap and the max diff must >= the average like [@DBabichev](https://leetcode.com/DBabichev) mentioned in the post, they can't all be lower than the average.

class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        lo = min(nums)
        hi = max(nums)
        n = len(nums)
        
        if n <= 2 or hi == lo: return hi - lo # edge case
        
        buckets = defaultdict(list)
        
        for x in nums:
            i = n - 2 if x == hi else (x - lo) * (n-1) // (hi - lo) # bucket formula, pidgeonhole principle
            buckets[i].append(x)
            
        cands = [ [min(buckets[i]), max(buckets[i])] for i in range(n-1) if buckets[i]] # min, max of each bucket
        return max(next[0] - prev[1] for prev, next in zip(cands, cands[1:]))

class Solution:
# @param num, a list of integer
# @return an integer
def maximumGap(self, num):
    if len(num) < 2 or min(num) == max(num):
        return 0
    a, b = min(num), max(num)
    size = math.ceil((b-a)/(len(num)-1))
    bucket = [[None, None] for _ in range((b-a)//size+1)]
    for n in num:
        b = bucket[(n-a)//size]
        b[0] = n if b[0] is None else min(b[0], n)
        b[1] = n if b[1] is None else max(b[1], n)
    bucket = [b for b in bucket if b[0] is not None]
    return max(bucket[i][0]-bucket[i-1][1] for i in range(1, len(bucket)))