LeetCode 164 - Maximum Gap

The problem asks us to compute the largest difference between two consecutive elements after sorting the array. At first glance, this may seem straightforward: sort the array, then scan through adjacent pairs to find the maximum difference.

leetcodemediumarraysortingbucket-sortradix-sort

LeetCode Problem 164

Difficulty: 🟡 Medium
Topics: Array, Sorting, Bucket Sort, Radix Sort

Solution

Problem Understanding

The problem asks us to compute the largest difference between two consecutive elements after sorting the array.

At first glance, this may seem straightforward: sort the array, then scan through adjacent pairs to find the maximum difference. However, there is an important constraint: the algorithm must run in linear time, O(n), and use linear extra space, O(n). This immediately rules out standard comparison-based sorting algorithms such as quicksort, mergesort, or heapsort, because they require O(n log n) time.

The input is an integer array nums, where each element represents a non-negative integer. We are asked to return the maximum gap between any two neighboring values in the array's sorted order.

For example:

nums = [3,6,9,1]

If we sort it:

[1,3,6,9]

The consecutive differences are:

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

The maximum difference is 3.

The output is therefore a single integer representing this maximum adjacent difference.

The constraints tell us several important things:

  • 1 <= nums.length <= 10^5, meaning the input can be very large, so inefficient solutions will time out.
  • 0 <= nums[i] <= 10^9, meaning values can be very large, so we cannot rely on small bounded ranges for counting sort.
  • We must achieve linear time, which strongly suggests using a non-comparison sorting strategy or exploiting a mathematical observation.

There are several important edge cases to consider upfront.

If the array contains fewer than two elements, there are no adjacent pairs, so the answer must be 0.

If all elements are identical, every difference is 0.

Very sparse ranges can create huge gaps. For example:

[1, 1000000]

The maximum gap is 999999.

Large duplicate groups can also cause mistakes if bucket boundaries are not handled carefully.

Approaches

Brute Force Approach

The simplest solution is to sort the array and then compute the maximum difference between adjacent elements.

The process is straightforward:

  1. Sort nums.
  2. Iterate through the sorted array.
  3. Compute differences between neighboring elements.
  4. Track the largest difference.

This works because after sorting, consecutive elements are exactly the pairs whose gap we care about.

However, sorting takes O(n log n) time, which violates the requirement for a linear-time solution.

For example:

nums = [3,6,9,1]

Sorted:

[1,3,6,9]

Adjacent gaps:

2, 3, 3

Maximum gap = 3.

Although correct, this approach is too slow for the problem's strict time complexity requirement.

Optimal Approach, Bucket Sort Using the Pigeonhole Principle

The key insight is that we do not actually need the fully sorted array.

We only need the largest adjacent gap.

Suppose:

  • min_num = minimum value
  • max_num = maximum value
  • n = number of elements

If we divide the range into buckets, we can use an important observation:

The maximum adjacent gap cannot occur inside a bucket, it must occur between buckets.

Why?

If bucket size is chosen carefully, numbers inside the same bucket are guaranteed to be relatively close together. Therefore, any very large gap must appear between the maximum of one bucket and the minimum of another.

We use the Pigeonhole Principle.

The minimum possible maximum gap is:

(max_num - min_num) / (n - 1)

This tells us an appropriate bucket size.

Each bucket stores only:

  • The minimum value inside it
  • The maximum value inside it

We do not need to store every element.

After placing all numbers into buckets, we scan bucket boundaries:

current_bucket_min - previous_bucket_max

The largest such value is the answer.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n log n) O(1) or O(n) Sort array and scan adjacent differences
Optimal O(n) O(n) Bucket sort using pigeonhole principle

Algorithm Walkthrough

Step 1: Handle Small Inputs

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

No adjacent comparison is possible.

Step 2: Find Global Minimum and Maximum

We determine:

min_num = min(nums)
max_num = max(nums)

These values define the overall range.

If:

min_num == max_num

all elements are identical, so return 0.

Step 3: Compute Bucket Size

We calculate the minimum guaranteed maximum gap:

bucket_size = max(1, (max_num - min_num) // (n - 1))

We use max(1, ...) to avoid division issues.

This bucket size ensures that any maximum gap must occur between buckets.

Step 4: Determine Number of Buckets

We compute:

bucket_count =
(max_num - min_num) // bucket_size + 1

Each bucket covers a continuous range.

For example:

nums = [1,3,6,9]

range = 8
bucket_size = 2
bucket_count = 5

Buckets:

[1-2]
[3-4]
[5-6]
[7-8]
[9-10]

Step 5: Initialize Buckets

Each bucket stores:

  • Minimum value
  • Maximum value

Initially:

bucket_min = [inf] * bucket_count
bucket_max = [-inf] * bucket_count

We also track whether a bucket is used.

Step 6: Place Numbers Into Buckets

For each number:

bucket_index =
(num - min_num) // bucket_size

Update:

bucket_min[index]
bucket_max[index]

Only extremes matter.

Step 7: Scan Buckets for Maximum Gap

We skip empty buckets.

For every non-empty bucket:

gap =
current_bucket_min - previous_bucket_max

Update maximum gap.

Then move forward:

previous_bucket_max =
current_bucket_max

Step 8: Return Result

The maximum inter-bucket difference is the answer.

Python Solution

from typing import List

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

        if n < 2:
            return 0

        min_num = min(nums)
        max_num = max(nums)

        if min_num == max_num:
            return 0

        bucket_size = max(
            1,
            (max_num - min_num) // (n - 1)
        )

        bucket_count = (
            (max_num - min_num)
            // bucket_size
        ) + 1

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

        for num in nums:
            bucket_index = (
                num - min_num
            ) // bucket_size

            bucket_min[bucket_index] = min(
                bucket_min[bucket_index],
                num
            )

            bucket_max[bucket_index] = max(
                bucket_max[bucket_index],
                num
            )

            bucket_used[bucket_index] = True

        max_gap = 0
        previous_max = min_num

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

            max_gap = max(
                max_gap,
                bucket_min[i] - previous_max
            )

            previous_max = bucket_max[i]

        return max_gap

The implementation begins by handling arrays with fewer than two elements. Since no adjacent comparison exists, the result is immediately 0.

Next, the global minimum and maximum values are found. These determine the numerical range we must cover with buckets. If all numbers are identical, every adjacent difference is zero.

The bucket size is then computed using the pigeonhole principle. This is the critical mathematical insight that guarantees the maximum gap appears between buckets rather than inside one.

Instead of storing every number, each bucket keeps only its minimum and maximum value. This greatly reduces memory usage while preserving all information needed to compute the answer.

Finally, the algorithm scans through the buckets. Empty buckets are skipped. For each non-empty bucket, we compute the difference between its minimum value and the previous bucket's maximum value. The largest such difference becomes the result.

Go Solution

func maximumGap(nums []int) int {
	n := len(nums)

	if n < 2 {
		return 0
	}

	minNum := nums[0]
	maxNum := nums[0]

	for _, num := range nums {
		if num < minNum {
			minNum = num
		}
		if num > maxNum {
			maxNum = num
		}
	}

	if minNum == maxNum {
		return 0
	}

	bucketSize := (maxNum - minNum) / (n - 1)
	if bucketSize < 1 {
		bucketSize = 1
	}

	bucketCount :=
		(maxNum-minNum)/bucketSize + 1

	const inf = int(^uint(0) >> 1)

	bucketMin := make([]int, bucketCount)
	bucketMax := make([]int, bucketCount)
	bucketUsed := make([]bool, bucketCount)

	for i := 0; i < bucketCount; i++ {
		bucketMin[i] = inf
		bucketMax[i] = -inf
	}

	for _, num := range nums {
		index :=
			(num - minNum) / bucketSize

		if num < bucketMin[index] {
			bucketMin[index] = num
		}

		if num > bucketMax[index] {
			bucketMax[index] = num
		}

		bucketUsed[index] = true
	}

	maxGap := 0
	previousMax := minNum

	for i := 0; i < bucketCount; i++ {
		if !bucketUsed[i] {
			continue
		}

		gap :=
			bucketMin[i] - previousMax

		if gap > maxGap {
			maxGap = gap
		}

		previousMax = bucketMax[i]
	}

	return maxGap
}

The Go implementation follows the same logic as Python, but there are a few language-specific differences.

Go does not have built-in infinity values for integers, so we simulate positive infinity using:

int(^uint(0) >> 1)

This represents the maximum integer value.

Instead of Python lists, Go uses slices initialized with make(). We also explicitly initialize bucket minimums and maximums because Go integers default to 0, which would break the logic for tracking extremes.

Go handles empty slices naturally, so no special nil handling is required beyond the length check.

Worked Examples

Example 1

Input:

nums = [3,6,9,1]

Step 1: Find Min and Max

Variable Value
min_num 1
max_num 9
n 4

Step 2: Compute Bucket Size

bucket_size =
(9 - 1) // (4 - 1)
= 2

Step 3: Create Buckets

bucket_count =
(9 - 1) // 2 + 1
= 5

Buckets:

Bucket Index Range
0 [1,2]
1 [3,4]
2 [5,6]
3 [7,8]
4 [9,10]

Step 4: Place Numbers

Number Bucket Bucket Min Bucket Max
3 1 3 3
6 2 6 6
9 4 9 9
1 0 1 1

Step 5: Scan Buckets

Bucket Gap Calculation Gap
0 1 - 1 0
1 3 - 1 2
2 6 - 3 3
4 9 - 6 3

Maximum gap:

3

Example 2

Input:

nums = [10]

Since:

n < 2

We immediately return:

0

No adjacent pair exists.

Complexity Analysis

Measure Complexity Explanation
Time O(n) One pass for min/max, one pass for bucket filling, one pass for scanning
Space O(n) Buckets require linear auxiliary memory

The algorithm achieves linear time because every element is processed a constant number of times. We never sort the array explicitly. Instead, bucket placement and bucket scanning each require only a single traversal.

The space complexity is linear because the number of buckets grows proportionally to the number of elements.

Edge Cases

Edge Case 1: Array With One Element

Consider:

[10]

There are no adjacent elements after sorting, so no gap exists. A naive implementation may accidentally attempt comparisons and cause index errors. Our solution handles this immediately with:

if n < 2:
    return 0

Edge Case 2: All Elements Are Equal

Consider:

[5,5,5,5]

Sorted form:

[5,5,5,5]

All gaps are zero.

This case is important because:

max_num - min_num = 0

which could cause division-by-zero problems when computing bucket size. Our implementation avoids this by returning 0 immediately when:

min_num == max_num

Edge Case 3: Large Numerical Gaps

Consider:

[1, 1000000000]

The maximum gap is:

999999999

A poor bucket strategy might overflow or create incorrect ranges. Our implementation computes bucket size dynamically and correctly places both values into separate buckets, preserving the large difference.

Edge Case 4: Duplicate Values

Consider:

[1,1,1,10]

Duplicates should not confuse bucket boundaries.

Sorted form:

[1,1,1,10]

Gaps:

0, 0, 9

The algorithm correctly tracks only bucket minimums and maximums, ensuring duplicates do not distort the final answer.