Maximum Gap
Given an integer array nums, return the maximum difference between two successive elements once the array is sorted. If the array contains fewer than two elements, return 0. Do it in linear time and linear extra space — comparison sorting is not allowed. Spread the values across buckets sized so that no two values in the same bucket can produce the maximum gap — then the answer only ever falls between the max of one bucket and the min of the next.
Constraints
- 1 ≤ nums.length ≤ 105
- 0 ≤ numsi ≤ 109
Example
nums = [3, 6, 9, 1]3Explanation Sorted, nums is [1, 3, 6, 9]. The gaps are 2, 3, and 3 — the maximum is 3.
In plain terms
- Bucket
- A range-based grouping. With n numbers spread across [min, max], at least one gap between successive buckets must be at least (max − min) / (n − 1) — so the maximum gap can never sit inside a single bucket.
Bucket the values, then compare only across bucket boundaries
nums=[3, 6, 9, 1]. min=1 (index 3), max=9 (index 2). Bucket size = ceil((9-1)/(4-1)) = 3.
What happens in this step
nums = [3, 6, 9, 1] lo = 1, hi = 9, bucketCount = n - 1 = 3 bucketSize = ceil((hi - lo) / bucketCount) = ceil(8 / 3) = 3 Bucket 0 covers values 1-3, bucket 1 covers 4-6, bucket 2 covers 7-9.
Steps to visualize
- Find the minimum and maximum values to size the buckets.
- Bucket size = ceil((max − min) / (n − 1)), so the max gap can never live inside one bucket.
- Place every value except the overall min and max into a bucket, tracking each bucket's own min and max.
- Walk the buckets in order, comparing each bucket's min to the previous bucket's max.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
nums=[3, 6, 9, 1]. min=1 (index 3), max=9 (index 2). Bucket size = ceil((9-1)/(4-1)) = 3.
What happens in this step
nums = [3, 6, 9, 1] lo = 1, hi = 9, bucketCount = n - 1 = 3 bucketSize = ceil((hi - lo) / bucketCount) = ceil(8 / 3) = 3 Bucket 0 covers values 1-3, bucket 1 covers 4-6, bucket 2 covers 7-9.
Solution
function maximumGap(nums) {
const n = nums.length;
if (n < 2) return 0;
let lo = nums[0];
let hi = nums[0];
for (const num of nums) {
if (num < lo) lo = num;
if (num > hi) hi = num;
}
if (lo === hi) return 0;
const bucketCount = n - 1;
const bucketSize = Math.max(1, Math.ceil((hi - lo) / bucketCount));
const bucketMin = new Array(bucketCount).fill(Infinity);
const bucketMax = new Array(bucketCount).fill(-Infinity);
for (const num of nums) {
if (num === lo || num === hi) continue;
let index = Math.floor((num - lo) / bucketSize);
if (index >= bucketCount) index = bucketCount - 1;
if (num < bucketMin[index]) bucketMin[index] = num;
if (num > bucketMax[index]) bucketMax[index] = num;
}
let maxGap = 0;
let prevMax = lo;
for (let i = 0; i < bucketCount; i++) {
if (bucketMax[i] === -Infinity) continue;
maxGap = Math.max(maxGap, bucketMin[i] - prevMax);
prevMax = bucketMax[i];
}
maxGap = Math.max(maxGap, hi - prevMax);
return maxGap;
}- Time
- O(n)
- Space
- O(n)
Test cases
| Input | Expected | Covers |
|---|---|---|
nums = [3, 6, 9, 1] | 3 | example from the docstring |
nums = [] | 0 | fewer than two elements returns 0 |
nums = [10] | 0 | a single element cannot form a gap |
nums = [1, 10000000] | 9999999 | two elements far apart, no buckets in between get filled |
nums = [5, 5, 5, 5] | 0 | every value is identical, so there is no gap at all |
nums = [-5, -1, -3, 2, 0] | 2 | negative and positive values mixed together |
nums = [1, 4, 7, 1000] | 993 | most values clustered together with one large outlier |