164. Maximum Gap

class Solution:
    def maximumGap(self, A: List[int]) -> int:
        """tc O(N) sc O(N)
        main idea:  since is required to write  in tc O(N) sc O(N) 
             since need to get max gap for each consecutive pair => wee need to sort => bucket sort 

            - with caculated avg gap, we can get max gap is not less than avg_gap 
            - if we hold min,max two values and assign at most n-2 items into n-1 buckets,  there must be empty buckets, so value pair consisting max gap will exist in two different bucket => compare current minBucket - prev maxBucket   
        0. edge case:  len < 2 or all values are same 
        1. get min max, get avg_gap
        2. create min max bucket and loop through array to assign each value based on avg_gap 
        3. at same index, compare each min bucket with previous index's max bucket. Note to avoid empty bucket 
        4. chekc last maxv with last maxBucket to update res 
        =======================================================================================
        1 3 6 8    avg_gap = ceil((8-1)//3) = 3   
        divide into bucket 
        [1,4)   [4,7)   [7,10)    n-1 = 3 buckets
         1 3     6        8     
          
          since for each bucket, only two end can be possible max diff pair, so we only record minvBucket and maxvBucket
          idx          0          1          2
          minvBucket   1          6          8
          maxvBucket   3          6          8  
          
          then we compare at each index, its minv - previous maxv, get the max diff 
                       NA         3          2        
        """
        n = len(A)
        if n < 2 or min(A) == max(A): # add for early termination 
            return 0
        minv,maxv = min(A),max(A)
        avg_gap = (maxv-minv-1)//(n-1)+1
        numBucket = n-1
        # get min,max at each interval 
        minvBucket = [float('inf')]*numBucket
        maxvBucket = [float('-inf')]*numBucket
        for a in A:
            if a in [minv,maxv]:
                continue 
            idx = (a-minv)//avg_gap
            minvBucket[idx] = min(minvBucket[idx],a) #if minvBucket[idx] != float('inf') else a 
            maxvBucket[idx] = max(maxvBucket[idx],a) #if maxvBucket[idx] != float('-inf') else a


        # check each consecutive bucket pair, get possible max diff from current minbucket - prev maxbucket 
        prev_max = minv 
        res = -1
        for i in range(numBucket):
            if minvBucket[i] == float('inf') and maxvBucket[i] == float('-inf'):  # empty bucket
                continue 
            res = max(res,minvBucket[i]-prev_max)
            prev_max = maxvBucket[i]
        res = max(res,maxv- prev_max) # update last possible max gap at maxv position since bucket range is [x,y) so maxv is not covered 
        #   e.g. A = [1,10000000]  only one bucket [1,10000000)
        return res