Leetcoding 164: Max Gap

One approach to solve this problem is to use the “Bucket Sort” algorithm. The basic idea is to divide the range of the elements into n-1 buckets, where n is the number of elements in the array. Each bucket contains a range of elements, and the maximum gap will be at least the size of the range of any two adjacent buckets.

Here is the solution in Python:

class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        if len(nums) < 2:
            return 0
        
        n = len(nums)
        max_num = max(nums)
        min_num = min(nums)
        bucket_size = max(1, (max_num - min_num) // (n - 1))
        bucket_count = (max_num - min_num) // bucket_size + 1
        buckets = [None] * bucket_count
        
        for num in nums:
            index = (num - min_num) // bucket_size
            if buckets[index] is None:
                buckets[index] = {'min': num, 'max': num}
            else:
                buckets[index]['min'] = min(buckets[index]['min'], num)
                buckets[index]['max'] = max(buckets[index]['max'], num)
        
        max_gap = 0
        previous_bucket_max = min_num
        for i in range(bucket_count):
            if buckets[i] is None:
                continue
            max_gap = max(max_gap, buckets[i]['min'] - previous_bucket_max)
            previous_bucket_max = buckets[i]['max']
        
        return max_gap

Big O Analysis:

The time complexity of this solution is O(n), where n is the number of elements in the array. This is because we loop through the elements once to fill the buckets, and once again to calculate the maximum gap. The space complexity is also O(n), as we need to store the buckets.