LeetCode 164: Maximum Gap

Problem Description

LeetCode Problem 164

Given an integer array nums, return the maximum difference between two successive elements in its sorted form. If the array contains less than two elements, return 0.

You must write an algorithm that runs in linear time and uses linear extra space.

Example 1:

Input: nums = [3,6,9,1]
Output: 3
Explanation: The sorted form of the array is [1,3,6,9], either (3,6) or (6,9) has the maximum difference 3.

Example 2:

Input: nums = [10]
Output: 0
Explanation: The array contains less than 2 elements, therefore return 0.

Constraints:

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 109

Difficulty: Medium

Tags: array, sorting, bucket sort, radix sort

Rating: 89.07%

Solution Approach: Bucket Sort

The key challenge in this problem is achieving O(n) time complexity. Regular sorting algorithms like quicksort or mergesort would give us O(n log n), which isn’t acceptable. This is where bucket sort comes in handy.

Key Insights

1. If we have n numbers spanning from min to max, the maximum gap must be at least ⌈(max - min)/(n-1)⌉
2. We can use this minimum possible gap as our bucket size
3. The maximum gap must occur between numbers in different buckets, not within the same bucket

Understanding the Math

1. Bucket Size Formula: (max_val - min_val) // (n-1)

   • With n numbers, we have n-1 gaps
   • Total range is max_val - min_val
   • Average gap = total range / number of gaps
   • Maximum gap must be ≥ average gap

2. Number of Buckets Formula: (max_val - min_val) // bucket_size + 1

   • We need enough buckets to cover the entire range
   • The +1 ensures we include both min_val and max_val
   • This effectively implements a ceiling division

Complexity Analysis

The solution has the following complexity characteristics:

• Time Complexity: O(n)

  • Finding min/max: O(n)
  • Creating and filling buckets: O(n)
  • Finding max gap: O(n)

• Space Complexity: O(n)

  • We need at most n buckets
  • Each number is stored exactly once

Solution

Here’s my Python solution to this problem:

class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        if len(nums) < 2: return 0
        
        minv, maxv = min(nums), max(nums)
        if minv == maxv: return 0

        n = len(nums)
        bucketsize = max(1, (maxv - minv) // (n-1)) #Minimum possible gap
        buckets = [[] for _ in range((maxv - minv) // bucketsize + 1)] # ceil((maxv - minv) / bucketsize)

        for n in nums:
            if n == maxv:
                idx = len(buckets) - 1
            else:
                idx = (n - minv) // bucketsize
            buckets[idx].append(n)

        #Remove empty buckets
        buckets = [b for b in buckets if b]

        #Find max gap
        maxgap = 0
        prevmax = max(buckets[0])

        for i in range(1, len(buckets)):
            currmin = min(buckets[i])
            maxgap = max(maxgap, currmin - prevmax)
            prevmax = max(buckets[i])

        return maxgap