Maximum Gap

The problem. Given an integer array nums, return the maximum difference between two successive elements in its sorted form. Return 0 if there are fewer than two elements. You must solve it in linear time and linear space.

Example

nums = [3, 6, 9, 1]          ->  3   (sorted 1, 3, 6, 9: every gap is 3)
nums = [1, 10, 5, 50, 52, 25] ->  25  (sorted 1, 5, 10, 25, 50, 52)
nums = [10]                   ->  0

The idea: the pigeonhole principle

Sorting and scanning neighbours is O(n log n) — too slow for the requirement. But we don't need the full order, only the largest gap. With n values between lo and hi, there are n − 1 gaps adding up to hi − lo, so the largest is at least the average, (hi − lo) / (n − 1).

So cut the range into buckets narrower than that. Two values in the same bucket are closer than the average gap, so the maximum gap never lies inside a bucket — it always runs from the largest value of one non-empty bucket to the smallest value of the next non-empty one. Each bucket only needs its min and max, and one scan over the buckets finds the answer: linear time, no sorting.

1. Sort, then scan neighbours

1function maximumGap(nums) {2  const a = [...nums].sort((x, y) => x - y);3  let best = 0;4  for (let i = 1; i < a.length; i++) best = Math.max(best, a[i] - a[i - 1]);5  return best;6}

Time O(n log n), space O(n). Correct, but it breaks the linear-time requirement. (Radix sort would make this approach linear for 32-bit integers too.)

2. Buckets

1function maximumGap(nums) {2  const n = nums.length;3  if (n < 2) return 0;4  const lo = Math.min(...nums), hi = Math.max(...nums);5  if (lo === hi) return 0;6  const size = Math.max(1, Math.floor((hi - lo) / (n - 1)));   // the biggest gap is at least this wide7  const count = Math.floor((hi - lo) / size) + 1;8  const bucketMin = new Array(count).fill(Infinity);9  const bucketMax = new Array(count).fill(-Infinity);10  for (const x of nums) {11    const b = Math.floor((x - lo) / size);12    bucketMin[b] = Math.min(bucketMin[b], x);13    bucketMax[b] = Math.max(bucketMax[b], x);14  }15  let best = 0, prevMax = lo;16  for (let b = 0; b < count; b++) {17    if (bucketMin[b] === Infinity) continue;          // empty bucket18    best = Math.max(best, bucketMin[b] - prevMax);    // gaps inside a bucket are never the biggest19    prevMax = bucketMax[b];20  }21  return best;22}

Time O(n), space O(n). There are about n buckets; filling them and scanning them are both linear. Why bucket width ⌊(hi − lo)/(n − 1)⌋ is safe: two values in one bucket differ by at most width − 1, which is less than the average gap and so less than the maximum gap.

Comparing the approaches

This is the hardest question in the chapter because the trick is a counting argument, not code: once you see that the maximum gap is at least the average gap, the buckets follow.

Edge cases to test

Variations