# Maximum Gap
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-gap)
Canonical: https://scaleengineer.com/dsa/problems/maximum-gap
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting), [Bucket Sort](https://scaleengineer.com/algorithms/bucket-sort), [Radix Sort](https://scaleengineer.com/algorithms/radix-sort)
**Data structures:** Array
**Companies:** [DoorDash](https://scaleengineer.com/companies/doordash)
---
## Problem
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`

# Approaches
## Comparison Sorting
The most straightforward approach is to sort the array first and then find the maximum difference between adjacent elements. This guarantees that we are comparing successive elements as required by the problem, as the maximum gap in the sorted version of the array must lie between two consecutive elements.
**Time:** O(N log N) · **Space:** O(log N) to O(N)
**Pros:** Very simple to understand and implement.; Leverages built-in, highly-optimized sorting functions.
**Cons:** The time complexity of O(N log N) does not meet the problem's requirement of a linear time algorithm.
### Explanation
This method leverages standard sorting algorithms. The core idea is that once the array is sorted, the two elements that form the maximum gap must be adjacent in the sorted sequence.

```java
import java.util.Arrays;

class Solution {
    public int maximumGap(int[] nums) {
        if (nums == null || nums.length < 2) {
            return 0;
        }
        
        Arrays.sort(nums);
        
        int maxGap = 0;
        for (int i = 1; i < nums.length; i++) {
            maxGap = Math.max(maxGap, nums[i] - nums[i-1]);
        }
        
        return maxGap;
    }
}
```
### Algorithm
- If the length of the input array `nums` is less than 2, return 0.
- Sort the array `nums` in ascending order. Most standard library sort functions have a time complexity of O(N log N).
- Initialize a variable `maxGap` to 0.
- Iterate through the sorted array from the second element (index 1) to the end.
- In each iteration, calculate the difference between the current element and its predecessor (`nums[i] - nums[i-1]`).
- Update `maxGap` to be the maximum of its current value and the calculated difference.
- After iterating through the entire array, return `maxGap`.

## Radix Sort
To meet the linear time requirement, we can replace the comparison-based sort with a linear-time sorting algorithm. Since the input consists of non-negative integers, Radix Sort is an excellent choice. It sorts the array in O(N) time, after which we can find the maximum gap in a single pass.
**Time:** O(N) · **Space:** O(N)
**Pros:** Achieves the required O(N) time complexity.; Satisfies the problem constraints.
**Cons:** Implementation is more complex than comparison sorting.; Can have a larger constant factor in its time complexity compared to the more specialized bucket sort approach.
### Explanation
Radix sort works by sorting numbers based on their individual digits, starting from the least significant digit and moving to the most significant. For each digit, it uses a stable sort (like counting sort) to arrange the numbers. Because the range of values for each digit (0-9) is small and the number of digits is constant for the given constraints (up to 10^9), the overall time complexity is linear.

```java
import java.util.Arrays;

class Solution {
    // Radix sort helper
    private void radixSort(int[] nums) {
        if (nums.length < 2) return;
        
        int maxVal = 0;
        for (int num : nums) {
            maxVal = Math.max(maxVal, num);
        }

        long exp = 1;
        int[] buffer = new int[nums.length];
        
        while (maxVal / exp > 0) {
            int[] count = new int[10];
            for (int num : nums) {
                count[(int)((num / exp) % 10)]++;
            }
            
            for (int i = 1; i < 10; i++) {
                count[i] += count[i - 1];
            }
            
            for (int i = nums.length - 1; i >= 0; i--) {
                buffer[--count[(int)((nums[i] / exp) % 10)]] = nums[i];
            }
            
            System.arraycopy(buffer, 0, nums, 0, nums.length);
            exp *= 10;
        }
    }

    public int maximumGap(int[] nums) {
        if (nums == null || nums.length < 2) {
            return 0;
        }
        
        radixSort(nums);
        
        int maxGap = 0;
        for (int i = 1; i < nums.length; i++) {
            maxGap = Math.max(maxGap, nums[i] - nums[i-1]);
        }
        
        return maxGap;
    }
}
```
### Algorithm
- If the array has fewer than two elements, return 0.
- Sort the array `nums` using Radix Sort. Radix sort processes numbers digit by digit (or by groups of bits) and uses a stable sorting subroutine like Counting Sort.
- For numbers up to 10^9, we can sort based on decimal digits or, more efficiently, by bytes.
- Once the array is sorted in linear time, initialize `maxGap` to 0.
- Perform a single pass through the sorted array from the second element.
- Calculate the difference `nums[i] - nums[i-1]` and update `maxGap` with the maximum difference found.
- Return `maxGap`.

## Bucket Sort / Pigeonhole Principle
The most optimal approach uses principles from Bucket Sort and the Pigeonhole Principle. It solves the problem in linear time and space without fully sorting the array. The key insight is that if we distribute the numbers into buckets of a certain size, the maximum gap cannot occur between two numbers that fall into the same bucket. Therefore, we only need to compare the boundaries of adjacent non-empty buckets.
**Time:** O(N) · **Space:** O(N)
**Pros:** Achieves optimal O(N) time and O(N) space complexity.; Highly efficient as it avoids a full sort and only requires a few passes over the data.
**Cons:** The logic is more complex and less intuitive than a simple sort.; Requires careful calculation of bucket size and handling of edge cases to work correctly.
### Explanation
This algorithm cleverly avoids a full sort. By creating buckets of size `b = (max - min) / (N - 1)`, we know the maximum gap must be at least `b`. Any two numbers within the same bucket can have a gap of at most `b-1`. Thus, the maximum gap can only be found by comparing the maximum value of a bucket with the minimum value of the next non-empty bucket. This reduces the number of comparisons from O(N) (in a sorted array) to O(num_buckets), which is also O(N).

```java
import java.util.Arrays;

class Solution {
    public int maximumGap(int[] nums) {
        if (nums == null || nums.length < 2) {
            return 0;
        }

        int n = nums.length;
        int minVal = nums[0];
        int maxVal = nums[0];
        for (int num : nums) {
            minVal = Math.min(minVal, num);
            maxVal = Math.max(maxVal, num);
        }

        if (maxVal == minVal) {
            return 0;
        }

        int bucketSize = Math.max(1, (maxVal - minVal) / (n - 1));
        int bucketCount = (maxVal - minVal) / bucketSize + 1;

        int[] bucketMin = new int[bucketCount];
        int[] bucketMax = new int[bucketCount];
        Arrays.fill(bucketMin, Integer.MAX_VALUE);
        Arrays.fill(bucketMax, Integer.MIN_VALUE);

        for (int num : nums) {
            int bucketIdx = (num - minVal) / bucketSize;
            bucketMin[bucketIdx] = Math.min(bucketMin[bucketIdx], num);
            bucketMax[bucketIdx] = Math.max(bucketMax[bucketIdx], num);
        }

        int maxGap = 0;
        int previousMax = minVal;
        for (int i = 0; i < bucketCount; i++) {
            if (bucketMin[i] == Integer.MAX_VALUE) { // Empty bucket
                continue;
            }
            
            maxGap = Math.max(maxGap, bucketMin[i] - previousMax);
            previousMax = bucketMax[i];
        }

        return maxGap;
    }
}
```
### Algorithm
- Handle the edge case: if the array has fewer than 2 elements, return 0.
- Find the minimum (`minVal`) and maximum (`maxVal`) elements in the array in one pass.
- If `minVal == maxVal`, all elements are identical, so return 0.
- Calculate an appropriate bucket size. A good choice is `bucketSize = max(1, (maxVal - minVal) / (N - 1))`. This ensures the maximum gap is at least `bucketSize`.
- Calculate the number of buckets needed: `bucketCount = (maxVal - minVal) / bucketSize + 1`.
- Create two arrays, `bucketMin` and `bucketMax`, of size `bucketCount` to store the minimum and maximum values for each bucket. Initialize them with sentinel values.
- Iterate through the input numbers. For each number `num`, calculate its bucket index `idx = (num - minVal) / bucketSize` and update the min/max values in `bucketMin[idx]` and `bucketMax[idx]`.
- Initialize `maxGap = 0` and `previousMax = minVal`.
- Iterate through the buckets. For each non-empty bucket, calculate the gap between its minimum value and the maximum value of the previous non-empty bucket (`bucketMin[i] - previousMax`). Update `maxGap` with this value.
- Update `previousMax` to the current bucket's maximum value.
- Return `maxGap`.

# Solutions
### CSharp

```csharp
using System ; using System.Linq ; public class Solution { public int MaximumGap ( int [] nums ) { if ( nums . Length < 2 ) return 0 ; var max = nums . Max (); var min = nums . Min (); var bucketSize = Math . Max ( 1 , ( max - min ) / ( nums . Length - 1 )); var buckets = new Tuple < int , int >[( max - min ) / bucketSize + 1 ]; foreach ( var num in nums ) { var index = ( num - min ) / bucketSize ; if ( buckets [ index ] == null ) { buckets [ index ] = Tuple . Create ( num , num ); } else { buckets [ index ] = Tuple . Create ( Math . Min ( buckets [ index ]. Item1 , num ), Math . Max ( buckets [ index ]. Item2 , num )); } } var result = 0 ; Tuple < int , int > lastBucket = null ; for ( var i = 0 ; i < buckets . Length ; ++ i ) { if ( buckets [ i ] != null ) { if ( lastBucket != null ) { result = Math . Max ( result , buckets [ i ]. Item1 - lastBucket . Item2 ); } lastBucket = buckets [ i ]; } } return result ; } }
```

### Java

```java
public class Maximum_Gap { public class Solution { public int maximumGap ( int [] nums ) { if ( nums == null || nums . length <= 1 ) { return 0 ; } // Step 1: find max and min element int max = Integer . MIN_VALUE ; int min = Integer . MAX_VALUE ; for ( int num : nums ) { if ( num > max ) { max = num ; } if ( num < min ) { min = num ; } } int len = nums . length ; // Step 2: calculate the intervals and number of buckets. int interval = ( int ) Math . ceil (( double ) ( max - min ) / ( len - 1 )); if ( interval == 0 ) { interval = 1 ; } int numBuckets = ( max - min ) / interval + 1 ; Bucket [] buckets = new Bucket [ numBuckets ]; for ( int i = 0 ; i < numBuckets ; i ++) { buckets [ i ] = new Bucket (); } // Step 3: iterate through the nums and assign the number into the buckets. for ( int num : nums ) { int bucketNum = ( num - min ) / interval ; if ( num > buckets [ bucketNum ]. max ) { buckets [ bucketNum ]. max = num ; } if ( num < buckets [ bucketNum ]. min ) { buckets [ bucketNum ]. min = num ; } } // Step 4: iterate through the buckets and get the maximal gap int prev = buckets [ 0 ]. max ; int maxGap = 0 ; for ( int i = 1 ; i < numBuckets ; i ++) { if ( prev != Integer . MIN_VALUE && buckets [ i ]. min != Integer . MAX_VALUE ) { maxGap = Math . max ( maxGap , buckets [ i ]. min - prev ); prev = buckets [ i ]. max ; } } return maxGap ; } private class Bucket { public int min ; public int max ; public Bucket () { min = Integer . MAX_VALUE ; max = Integer . MIN_VALUE ; } } } } ////// class Solution { public int maximumGap ( int [] nums ) { int n = nums . length ; if ( n < 2 ) { return 0 ; } int inf = 0x3f3f3f3f ; int mi = inf , mx = - inf ; for ( int v : nums ) { mi = Math . min ( mi , v ); mx = Math . max ( mx , v ); } int bucketSize = Math . max ( 1 , ( mx - mi ) / ( n - 1 )); int bucketCount = ( mx - mi ) / bucketSize + 1 ; int [][] buckets = new int [ bucketCount ][ 2 ]; for ( var bucket : buckets ) { bucket [ 0 ] = inf ; bucket [ 1 ] = - inf ; } for ( int v : nums ) { int i = ( v - mi ) / bucketSize ; buckets [ i ][ 0 ] = Math . min ( buckets [ i ][ 0 ], v ); buckets [ i ][ 1 ] = Math . max ( buckets [ i ][ 1 ], v ); } int prev = inf ; int ans = 0 ; for ( var bucket : buckets ) { if ( bucket [ 0 ] > bucket [ 1 ]) { continue ; } ans = Math . max ( ans , bucket [ 0 ] - prev ); prev = bucket [ 1 ]; } return ans ; } }
```

### Python

```python
''' >>> math.inf inf >>> 1 + math.inf inf >>> -1 - math.inf -inf ''' class Solution : def maximumGap ( self , nums : List [ int ]) -> int : n = len ( nums ) if n < 2 : return 0 mi , mx = min ( nums ), max ( nums ) # also passing OJ: # bucket_size = max(1, (mx - mi) // (n - 1)) bucket_size = max ( 1 , ( mx - mi ) // n ) bucket_count = ( mx - mi ) // bucket_size + 1 buckets = [[ inf , - inf ] for _ in range ( bucket_count )] for v in nums : i = ( v - mi ) // bucket_size buckets [ i ][ 0 ] = min ( buckets [ i ][ 0 ], v ) buckets [ i ][ 1 ] = max ( buckets [ i ][ 1 ], v ) ans = 0 prev = inf for curmin , curmax in buckets : if curmin > curmax : continue ans = max ( ans , curmin - prev ) prev = curmax return ans ############ class Solution ( object ): def maximumGap ( self , nums ): """ :type nums: List[int] :rtype: int """ if len ( nums ) < 2 : return 0 a , b = min ( nums ), max ( nums ) if a == b : return 0 ans = 0 gap = int ( math . ceil (( b - a + 0.0 ) / ( len ( nums ) - 1 ))) bucketMin = [ None for _ in range ( 0 , len ( nums ) + 1 )] bucketMax = [ None for _ in range ( 0 , len ( nums ) + 1 )] for num in nums : index = ( num - a ) / gap if bucketMin [ index ] is None : bucketMin [ index ] = num else : bucketMin [ index ] = min ( bucketMin [ index ], num ) if bucketMax [ index ] is None : bucketMax [ index ] = num else : bucketMax [ index ] = max ( bucketMax [ index ], num ) bucketMin = [ b for b in bucketMin if b is not None ] bucketMax = [ b for b in bucketMax if b is not None ] for i in range ( 0 , len ( bucketMin ) - 1 ): ans = max ( ans , bucketMin [ i + 1 ] - bucketMax [ i ]) return ans
```

### CPP

```cpp
// OJ: https://leetcode.com/problems/maximum-gap/ // Time: O(N) // Space: O(N) // Ref: https://discuss.leetcode.com/topic/5999/bucket-sort-java-solution-with-explanation-o-n-time-and-space class Solution { public: int maximumGap ( vector < int >& A ) { if ( A . size () == 1 ) return 0 ; int minVal = * min_element ( begin ( A ), end ( A )); int maxVal = * max_element ( begin ( A ), end ( A )); int N = A . size (), gap = ( maxVal - minVal + N - 2 ) / ( N - 1 ); vector < int > mn ( N - 1 , INT_MAX ), mx ( N - 1 , INT_MIN ); for ( int n : A ) { if ( n == minVal || n == maxVal ) continue ; int i = ( n - minVal ) / gap ; mn [ i ] = min ( mn [ i ], n ); mx [ i ] = max ( mx [ i ], n ); } int ans = gap , prev = minVal ; for ( int i = 0 ; i < N - 1 ; ++ i ) { if ( mn [ i ] == INT_MAX ) continue ; ans = max ( ans , mn [ i ] - prev ); prev = mx [ i ]; } return max ( ans , maxVal - prev ); } };
```