Maximum Gap

MediumBucket Sort · Pigeonhole🧩 Bucket & Counting Sort LeetCode #164 ↗Updated Oct 30, 2026

Problem

Given an array nums of non-negative integers, imagine it sorted and return the largest difference between two neighbours in that sorted order. If the array has fewer than two elements, return 0. The intended solution runs in linear time and linear extra space.

Input[3,6,9,1]Output3 (sorted 1,3,6,9)

Input[10]Output0

Input[1,10000000]Output9999999

1 ≤ n ≤ 10⁵ · 0 ≤ nums[i] ≤ 10⁹ · O(n) time and space required

Try it yourself

Java

class Solution {
    public int maximumGap(int[] nums) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

With n numbers spread over [lo, hi], the biggest gap is at least (hi - lo) / (n - 1). Use buckets narrower than that: no answer can live inside one bucket, so you only need each bucket's min and max.

PatternBucket & Counting Sort

Instinct Keys live in a small, known range (letters, frequencies 1..n, bounded values) - index an array by the key instead of comparing, and get O(n).

Memory hack Don't compare, just file it - every value walks straight to its own pigeonhole, then you read the shelves in order.

Open the Bucket & Counting Sort guide →

Approaches

Brute ForceSort, then Scan Neighbours

Time O(n log n)Space O(log n)

Sort a copy and compare each element with the one before it, keeping the largest difference. Sorting puts every candidate pair side by side, so a single scan finds the answer.

Java

public int maximumGap(int[] nums) {
    if (nums.length < 2) return 0;
    int[] a = nums.clone();
    Arrays.sort(a);
    int best = 0;
    for (int i = 1; i < a.length; i++) best = Math.max(best, a[i] - a[i - 1]);
    return best;
}

Three lines and obviously right, but comparison sorting misses the linear bound.

BetterLSD Radix Sort (Base 256)

Time O(4·(n + 256))Space O(n)

Sorting non-negative ints doesn't need comparisons: counting-sort by the lowest byte, then the next byte, and so on (4 stable passes). Stability means each pass keeps the order from the lower bytes, so after the last pass the array is sorted.

Java

public int maximumGap(int[] nums) {
    int n = nums.length;
    if (n < 2) return 0;
    int[] a = nums.clone(), buf = new int[n];
    for (int shift = 0; shift < 32; shift += 8) {
        int[] start = new int[257];
        for (int x : a) start[((x >>> shift) & 255) + 1]++;
        for (int d = 0; d < 256; d++) start[d + 1] += start[d]; // first slot per byte
        for (int x : a) buf[start[(x >>> shift) & 255]++] = x;  // stable placement
        int[] t = a; a = buf; buf = t;
    }
    int best = 0;
    for (int i = 1; i < n; i++) best = Math.max(best, a[i] - a[i - 1]);
    return best;
}

Linear time, but it still sorts everything and does four full passes.

OptimalPigeonhole Buckets (Min/Max Only)

Time O(n)Space O(n)

Bucket width w = max(1, (hi - lo) / (n - 1)) never exceeds the average gap, so any two numbers in the same bucket differ by less than the answer. The maximum gap is therefore between the max of one non-empty bucket and the min of the next non-empty one.

Java

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)); // <= smallest possible max gap
    int count = (hi - lo) / width + 1;
    int[] bMin = new int[count], bMax = new int[count];
    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 best = 0, prevMax = lo;
    for (int b = 0; b < count; b++) {
        if (bMin[b] == Integer.MAX_VALUE) continue; // empty bucket
        best = Math.max(best, bMin[b] - prevMax);
        prevMax = bMax[b];
    }
    return best;
}

Dry run[3,6,9,1]: lo=1, hi=9, width=8/3=2, 5 buckets

p prevMax bucketb current bucket changed

fill
1

3

6

·

9

bucket = (x-1)/2
b=0
1
b p
3

6

·

9

prevMax=1, best=0
b=1
1
p
3
b
6

·

9

3-1=2, best=2
b=2
1

3
p
6
b
·

9

6-3=3, best=3
b=3
1

3

6
p
·
b
9

empty → skip
b=4
1

3

6
p
·

9
b
9-6=3, best=3 ✔

True linear time without sorting — the intended answer.

Pro tip

Say the pigeonhole argument out loud: n-1 gaps share a total of hi-lo, so one of them is at least the average — that is why buckets may ignore their insides.

At a glance

Level	Approach	Time	Space
Brute Force	Sort, then Scan Neighbours	`O(n log n)`	`O(log n)`
Better	LSD Radix Sort (Base 256)	`O(4·(n + 256))`	`O(n)`
Optimal	Pigeonhole Buckets (Min/Max Only)	`O(n)`	`O(n)`

Common pitfalls

Bucket width of 0 when hi - lo < n - 1 — clamp it to at least 1.
Comparing only adjacent bucket indices instead of skipping empty buckets.
Not handling n < 2 or all-equal values (division by zero / wrong count).

Interview tips

Start with sort-and-scan, then ask whether O(n log n) is acceptable given the linear-time requirement.
Mention radix sort as a linear alternative before introducing buckets.
Prove the bucket trick with the average-gap lower bound; interviewers look for that argument.

Pattern

Bucket / pigeonhole by value range → need order statistics in O(n) when values span a known range.

My notes saved in this browser