Maximum Gap

medium array sorting bucket sort

Problem

Given an unsorted array nums of integers, return the maximum difference between two successive elements in its sorted form. If the array has fewer than two elements, return 0. Solve it in O(n) time and O(n) space.

Inputnums = [3, 6, 9, 1]

Output3

Sorted: [1, 3, 6, 9]. Gaps: 2, 3, 3. Max = 3. With n elements in [min, max], split the range into n−1 buckets of width ceil((max−min)/(n−1)); by pigeonhole the max gap spans a bucket boundary.

nums (comma-separated)

def maximum_gap(nums):
    n = len(nums)
    if n < 2: return 0
    lo, hi = min(nums), max(nums)
    if lo == hi: return 0
    width = max(1, (hi - lo) // (n - 1))
    bcount = (hi - lo) // width + 1
    bmin = [None] * bcount
    bmax = [None] * bcount
    for x in nums:
        b = (x - lo) // width
        bmin[b] = x if bmin[b] is None else min(bmin[b], x)
        bmax[b] = x if bmax[b] is None else max(bmax[b], x)
    gap, prev = 0, lo
    for i in range(bcount):
        if bmin[i] is None: continue
        gap = max(gap, bmin[i] - prev)
        prev = bmax[i]
    return gap

function maximumGap(nums) {
  const n = nums.length;
  if (n < 2) return 0;
  let lo = Math.min(...nums), hi = Math.max(...nums);
  if (lo === hi) return 0;
  const width = Math.max(1, Math.floor((hi - lo) / (n - 1)));
  const bc = Math.floor((hi - lo) / width) + 1;
  const bmin = Array(bc).fill(null), bmax = Array(bc).fill(null);
  for (const x of nums) {
    const b = Math.floor((x - lo) / width);
    bmin[b] = bmin[b] === null ? x : Math.min(bmin[b], x);
    bmax[b] = bmax[b] === null ? x : Math.max(bmax[b], x);
  }
  let gap = 0, prev = lo;
  for (let i = 0; i < bc; i++) {
    if (bmin[i] === null) continue;
    gap = Math.max(gap, bmin[i] - prev);
    prev = bmax[i];
  }
  return gap;
}

class Solution {
    public int maximumGap(int[] nums) {
        int n = nums.length;
        if (n < 2) return 0;
        int lo = Integer.MAX_VALUE, hi = Integer.MIN_VALUE;
        for (int x : nums) { lo = Math.min(lo, x); hi = Math.max(hi, x); }
        if (lo == hi) return 0;
        int width = Math.max(1, (hi - lo) / (n - 1));
        int bc = (hi - lo) / width + 1;
        int[] bmin = new int[bc], bmax = new int[bc];
        Arrays.fill(bmin, Integer.MAX_VALUE);
        Arrays.fill(bmax, Integer.MIN_VALUE);
        for (int x : nums) {
            int b = (x - lo) / width;
            bmin[b] = Math.min(bmin[b], x);
            bmax[b] = Math.max(bmax[b], x);
        }
        int gap = 0, prev = lo;
        for (int i = 0; i < bc; i++) {
            if (bmin[i] == Integer.MAX_VALUE) continue;
            gap = Math.max(gap, bmin[i] - prev);
            prev = bmax[i];
        }
        return gap;
    }
}

int maximumGap(vector<int>& nums) {
    int n = nums.size();
    if (n < 2) return 0;
    int lo = *min_element(nums.begin(), nums.end());
    int hi = *max_element(nums.begin(), nums.end());
    if (lo == hi) return 0;
    int width = max(1, (hi - lo) / (n - 1));
    int bc = (hi - lo) / width + 1;
    vector<int> bmin(bc, INT_MAX), bmax(bc, INT_MIN);
    for (int x : nums) {
        int b = (x - lo) / width;
        bmin[b] = min(bmin[b], x);
        bmax[b] = max(bmax[b], x);
    }
    int gap = 0, prev = lo;
    for (int i = 0; i < bc; i++) {
        if (bmin[i] == INT_MAX) continue;
        gap = max(gap, bmin[i] - prev);
        prev = bmax[i];
    }
    return gap;
}

Explanation

We need the biggest gap between neighbors once the array is sorted, but the catch is doing it in linear time — so we can't actually sort. The clever trick is bucket sort by spacing, using the pigeonhole principle.

If there are n numbers spread between lo and hi, the largest gap must be at least the average spacing (hi - lo) / (n - 1). So we make buckets of exactly that width. Because each bucket is no wider than that average, the biggest gap can never fit inside a single bucket — it must jump from one bucket to the next.

For each bucket we only keep its minimum and maximum value (bmin and bmax); we don't care about anything in between. Then we sweep the buckets left to right and measure each gap as "this bucket's min minus the previous bucket's max".

Example: [3,6,9,1], so lo=1, hi=9, n=4, width = 8/3 = 2. The numbers land in buckets, and scanning across them produces gaps like 3-1=2 and 6-3=3.

The largest of those, 3, is the answer — found without ever fully sorting.

Time: O(n) Space: O(n)