LeetCode 164: Maximum Gap

Problem Restatement

We are given an integer array nums.

We need to imagine the array sorted in ascending order, then return the maximum difference between two successive elements.

If the array has fewer than two elements, return 0.

The problem also requires an algorithm that runs in linear time and uses linear extra space. LeetCode states the constraints as 1 <= nums.length <= 10^5 and 0 <= nums[i] <= 10^9.

Input and Output

Example function shape:

def maximumGap(nums: list[int]) -> int:
    ...

Examples

Example 1:

nums = [3, 6, 9, 1]

Sorted form:

[1, 3, 6, 9]

Adjacent gaps:

3 - 1 = 2
6 - 3 = 3
9 - 6 = 3

The maximum gap is:

3

Example 2:

nums = [10]

There is only one number, so there is no adjacent pair.

Return:

0

Example 3:

nums = [1, 1, 1, 1]

Sorted form is the same.

Every adjacent gap is 0.

Return:

0

First Thought: Sort the Array

The direct solution is to sort the array, then scan adjacent pairs.

class Solution:
    def maximumGap(self, nums: list[int]) -> int:
        if len(nums) < 2:
            return 0

        nums.sort()
        answer = 0

        for i in range(1, len(nums)):
            answer = max(answer, nums[i] - nums[i - 1])

        return answer

This is simple and correct.

But comparison sorting takes:

O(n log n)

The problem asks for linear time, so we need a non-comparison approach.

Key Insight

Let:

mn = min(nums)
mx = max(nums)
n = len(nums)

There are n numbers and therefore n - 1 gaps between adjacent numbers in sorted order.

The total distance from the smallest number to the largest number is:

mx - mn

If all gaps were as even as possible, the average gap would be:

(mx - mn) / (n - 1)

So the maximum gap must be at least the ceiling of that value.

This gives us a useful bucket size:

bucket_size = ceil((mx - mn) / (n - 1))

When we place numbers into buckets of this size, any two numbers inside the same bucket have a gap smaller than or equal to the bucket size.

The maximum gap must occur between two non-empty buckets, not inside one bucket.

So each bucket only needs to remember two values:

Then we scan buckets from left to right and compare:

current_bucket_min - previous_bucket_max

Why Buckets Work

Suppose the sorted numbers are spread from mn to mx.

There must be at least one adjacent gap of size:

ceil((mx - mn) / (n - 1))

or larger.

If we create buckets using this size, the largest gap cannot be hidden inside a bucket. Values inside one bucket are too close together.

The gap we need appears when we move from one non-empty bucket to the next non-empty bucket.

That is why we do not need to sort every number inside each bucket.

We only need each bucket’s minimum and maximum.

Algorithm

Handle small cases:

if len(nums) < 2:
    return 0

Find:

mn = min(nums)
mx = max(nums)

If all numbers are the same:

if mn == mx:
    return 0

Compute bucket size using ceiling division:

bucket_size = max(1, (mx - mn + n - 2) // (n - 1))

Compute bucket count:

bucket_count = (mx - mn) // bucket_size + 1

Create arrays for bucket minimum and maximum.

For each number:

1. Compute its bucket index.
2. Update that bucket’s minimum.
3. Update that bucket’s maximum.

Then scan buckets in order:

1. Skip empty buckets.
2. Compare current bucket minimum with previous non-empty bucket maximum.
3. Update the answer.
4. Set previous maximum to current bucket maximum.

Walkthrough

Use:

nums = [3, 6, 9, 1]

Find:

mn = 1
mx = 9
n = 4

The value range is:

mx - mn = 8

There are:

n - 1 = 3

gaps in sorted order.

Bucket size:

ceil(8 / 3) = 3

Buckets by range:

Place numbers:

Bucket values:

Scan buckets:

Gap between bucket 0 and bucket 1:

6 - 3 = 3

Gap between bucket 1 and bucket 2:

9 - 6 = 3

Return:

3

Correctness

Let bucket_size be the ceiling of (mx - mn) / (n - 1).

Every number belongs to exactly one bucket according to its distance from mn.

Inside one bucket, the difference between any two numbers is less than or equal to the bucket range. Since the maximum adjacent gap in sorted order is at least bucket_size, the true maximum gap can be found between two neighboring non-empty buckets.

For two consecutive non-empty buckets, all numbers in the earlier bucket are less than or equal to all numbers in the later bucket. Therefore, the only candidate gap between these two groups is:

current_bucket_min - previous_bucket_max

The algorithm scans every pair of consecutive non-empty buckets and computes exactly this value.

Because every sorted adjacent pair is either inside one bucket or crosses from one non-empty bucket to the next, and the maximum gap must be one of the crossing gaps, the algorithm returns the correct maximum gap.

Complexity

Let n be the length of nums.

Implementation

class Solution:
    def maximumGap(self, nums: list[int]) -> int:
        n = len(nums)

        if n < 2:
            return 0

        mn = min(nums)
        mx = max(nums)

        if mn == mx:
            return 0

        bucket_size = max(1, (mx - mn + n - 2) // (n - 1))
        bucket_count = (mx - mn) // bucket_size + 1

        bucket_min = [float("inf")] * bucket_count
        bucket_max = [float("-inf")] * bucket_count
        bucket_used = [False] * bucket_count

        for num in nums:
            idx = (num - mn) // bucket_size

            bucket_min[idx] = min(bucket_min[idx], num)
            bucket_max[idx] = max(bucket_max[idx], num)
            bucket_used[idx] = True

        answer = 0
        previous_max = mn

        for i in range(bucket_count):
            if not bucket_used[i]:
                continue

            answer = max(answer, bucket_min[i] - previous_max)
            previous_max = bucket_max[i]

        return answer

Code Explanation

We first handle arrays with fewer than two elements:

if n < 2:
    return 0

Then find the smallest and largest values:

mn = min(nums)
mx = max(nums)

If they are equal, all values are the same:

if mn == mx:
    return 0

Compute bucket size with ceiling division:

bucket_size = max(1, (mx - mn + n - 2) // (n - 1))

The expression:

(a + b - 1) // b

computes ceil(a / b) for positive integers. Here a = mx - mn and b = n - 1.

Then compute how many buckets are needed:

bucket_count = (mx - mn) // bucket_size + 1

Each bucket tracks its minimum and maximum:

bucket_min = [float("inf")] * bucket_count
bucket_max = [float("-inf")] * bucket_count
bucket_used = [False] * bucket_count

For each number, compute its bucket:

idx = (num - mn) // bucket_size

and update the bucket’s range:

bucket_min[idx] = min(bucket_min[idx], num)
bucket_max[idx] = max(bucket_max[idx], num)
bucket_used[idx] = True

Finally, scan non-empty buckets:

answer = max(answer, bucket_min[i] - previous_max)
previous_max = bucket_max[i]

The answer is the largest gap between the minimum of a bucket and the maximum of the previous non-empty bucket.

Alternative: Radix Sort

Another linear-time approach is radix sort.

Since nums[i] is non-negative and at most 10^9, we can sort by digits in base 10 or base 256, then scan adjacent values.

Bucket-based gap finding is usually shorter for this problem because it avoids fully sorting the array.

Testing

def run_tests():
    sol = Solution()

    assert sol.maximumGap([3, 6, 9, 1]) == 3
    assert sol.maximumGap([10]) == 0
    assert sol.maximumGap([1, 1, 1, 1]) == 0
    assert sol.maximumGap([1, 10000000]) == 9999999
    assert sol.maximumGap([1, 3, 100]) == 97
    assert sol.maximumGap([10, 7, 1, 3]) == 4
    assert sol.maximumGap([0, 0, 1, 1]) == 1
    assert sol.maximumGap([15252, 16764, 27963, 7817, 26155]) == 11065

    print("all tests passed")

run_tests()