Maximum Gap (Bucket Sort Approach)

Problem Statement

Given an unsorted array, return the maximum difference between two successive elements once the array is sorted. Must run in linear time and space.

Example

Input:  [3, 6, 9, 1]
Output: 3  (sorted: 1,3,6,9 -> gaps 2,3,3)

Approach

By the pigeonhole principle, if you place n numbers into n buckets of equal width (max-min)/(n-1), the maximum gap must occur between buckets, not inside one. Track each bucket’s min and max, then scan buckets in order comparing each bucket’s min with the previous bucket’s max.

Complexity

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

Solution Code

Python

def maximumGap(nums):
    if len(nums) < 2:
        return 0
    lo, hi = min(nums), max(nums)
    if lo == hi:
        return 0
    n = len(nums)
    size = max(1, (hi - lo) // (n - 1))
    count = (hi - lo) // size + 1
    buckets = [[None, None] for _ in range(count)]  # [min, max]
    for x in nums:
        b = (x - lo) // size
        if buckets[b][0] is None:
            buckets[b] = [x, x]
        else:
            buckets[b][0] = min(buckets[b][0], x)
            buckets[b][1] = max(buckets[b][1], x)
    result, prev_hi = 0, lo
    for mn, mx in buckets:
        if mn is None:
            continue
        result = max(result, mn - prev_hi)
        prev_hi = mx
    return result

Java

int maximumGap(int[] nums) {
    int n = nums.length;
    if (n < 2) return 0;
    int lo = nums[0], hi = nums[0];
    for (int x : nums) { lo = Math.min(lo, x); hi = Math.max(hi, x); }
    if (lo == hi) return 0;
    int size = Math.max(1, (hi - lo) / (n - 1));
    int count = (hi - lo) / size + 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) / size;
        bMin[b] = Math.min(bMin[b], x);
        bMax[b] = Math.max(bMax[b], x);
    }
    int result = 0, prevHi = lo;
    for (int i = 0; i < count; i++) {
        if (bMin[i] == Integer.MAX_VALUE) continue;
        result = Math.max(result, bMin[i] - prevHi);
        prevHi = bMax[i];
    }
    return result;
}

C++

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 size = max(1, (hi - lo) / (n - 1));
    int count = (hi - lo) / size + 1;
    vector<int> bMin(count, INT_MAX), bMax(count, INT_MIN);
    for (int x : nums) {
        int b = (x - lo) / size;
        bMin[b] = min(bMin[b], x);
        bMax[b] = max(bMax[b], x);
    }
    int result = 0, prevHi = lo;
    for (int i = 0; i < count; i++) {
        if (bMin[i] == INT_MAX) continue;
        result = max(result, bMin[i] - prevHi);
        prevHi = bMax[i];
    }
    return result;
}

Key Takeaways

• The pigeonhole principle guarantees the max gap is between buckets.
• Only each bucket’s min and max matter — no need to sort inside buckets.
• Reference: LeetCode 164 (Maximum Gap).