# 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

| Item | Meaning |
|---|---|
| Input | Integer array `nums` |
| Output | Maximum difference between adjacent values after sorting |
| Small array rule | Return `0` if there are fewer than two values |
| Required time | Linear time |
| Required space | Linear extra space |

Example function shape:

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

## Examples

Example 1:

```python
nums = [3, 6, 9, 1]
```

Sorted form:

```python
[1, 3, 6, 9]
```

Adjacent gaps:

```python
3 - 1 = 2
6 - 3 = 3
9 - 6 = 3
```

The maximum gap is:

```python
3
```

Example 2:

```python
nums = [10]
```

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

Return:

```python
0
```

Example 3:

```python
nums = [1, 1, 1, 1]
```

Sorted form is the same.

Every adjacent gap is `0`.

Return:

```python
0
```

## First Thought: Sort the Array

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

```python
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:

```python
O(n log n)
```

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

## Key Insight

Let:

```python
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:

```python
mx - mn
```

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

```python
(mx - mn) / (n - 1)
```

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

This gives us a useful bucket size:

```python
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:

| Bucket field | Meaning |
|---|---|
| Minimum | Smallest value in this bucket |
| Maximum | Largest value in this bucket |

Then we scan buckets from left to right and compare:

```python
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:

```python
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:

```python
if len(nums) < 2:
    return 0
```

Find:

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

If all numbers are the same:

```python
if mn == mx:
    return 0
```

Compute bucket size using ceiling division:

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

Compute bucket count:

```python
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:

```python
nums = [3, 6, 9, 1]
```

Find:

```python
mn = 1
mx = 9
n = 4
```

The value range is:

```python
mx - mn = 8
```

There are:

```python
n - 1 = 3
```

gaps in sorted order.

Bucket size:

```python
ceil(8 / 3) = 3
```

Buckets by range:

| Bucket | Range |
|---|---|
| `0` | `1` to `3` |
| `1` | `4` to `6` |
| `2` | `7` to `9` |

Place numbers:

| Number | Bucket |
|---|---|
| `1` | `0` |
| `3` | `0` |
| `6` | `1` |
| `9` | `2` |

Bucket values:

| Bucket | Min | Max |
|---|---|---|
| `0` | `1` | `3` |
| `1` | `6` | `6` |
| `2` | `9` | `9` |

Scan buckets:

Gap between bucket `0` and bucket `1`:

```python
6 - 3 = 3
```

Gap between bucket `1` and bucket `2`:

```python
9 - 6 = 3
```

Return:

```python
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:

```python
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`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We find min and max, fill buckets, then scan buckets |
| Space | `O(n)` | The number of buckets is linear in `n` |

## Implementation

```python
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:

```python
if n < 2:
    return 0
```

Then find the smallest and largest values:

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

If they are equal, all values are the same:

```python
if mn == mx:
    return 0
```

Compute bucket size with ceiling division:

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

The expression:

```python
(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:

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

Each bucket tracks its minimum and maximum:

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

For each number, compute its bucket:

```python
idx = (num - mn) // bucket_size
```

and update the bucket’s range:

```python
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:

```python
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

```python
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()
```

| Test | Why |
|---|---|
| `[3, 6, 9, 1]` | Standard example |
| `[10]` | Fewer than two elements |
| `[1, 1, 1, 1]` | All values equal |
| `[1, 10000000]` | Large numeric gap |
| `[1, 3, 100]` | Maximum gap near the end |
| `[10, 7, 1, 3]` | Unsorted input |
| `[0, 0, 1, 1]` | Duplicates with small gap |
| Larger mixed values | Checks bucket indexing |