Maximum Gap — Editorial

Opening the reading…

Intuitionwhy the largest gap survives bucket compression

If n values are placed between the minimum and maximum, there are n - 1 consecutive gaps in sorted order. Their total is maxVal - minVal, so at least one gap is at least the average range divided by n - 1. That lower bound tells you how wide a bucket can be before two values inside one bucket are unable to form the answer.

Choose bucketSize as the integer floor of (maxVal - minVal) / (n - 1), with a minimum of 1. Any two distinct values in one bucket differ by at most bucketSize - 1, so the maximum gap cannot be completely inside a bucket. It must run from the maximum value in one non-empty bucket to the minimum value in the next non-empty bucket. Each bucket therefore needs only a minimum and a maximum, not its contents.

Approach

Return 0 when there are fewer than two values, because no pair of successive sorted elements exists and the bucket formula would divide by n - 1.

Find minVal and maxVal, because every bucket index is computed relative to the global minimum and the total range determines the bucket width.

Set bucketSize to max(1, (maxVal - minVal) / (n - 1)), because a zero width would make indexing invalid and this width guarantees that a gap inside one bucket cannot be the maximum.

Create bucketMin and bucketMax arrays filled with INT_MAX and INT_MIN, because an untouched bucket must be distinguishable from a bucket containing a real value.

Map each number to (num - minVal) / bucketSize and update only that bucket's minimum and maximum, because values in the same bucket cannot determine the answer internally.

Scan buckets from left to right, skip empty buckets, and compare the current bucket's minimum with the previous non-empty bucket's maximum, because every possible maximum gap lies across that boundary.

Update prevMax only after processing a non-empty bucket, then return the largest comparison, because empty buckets contain no sorted value that can become the previous endpoint.

Complexitylinear work and linear bucket storage

MEASURE	BOUND	WHY
Time	O(n)	Finding the extrema scans n values, placing values scans n values, and scanning the bucket array takes O(n) buckets because the bucket width is at least 1 and the value range is at most n - 1 bucket widths plus a remainder. These three passes are sequential, so their costs add to O(n).
Space	O(n) extra	The two bucket arrays have O(n) entries, and the returned result is only one integer and is required output rather than working memory. The bound remains O(n) in the widest possible value range; duplicate values and a narrow range only reduce the actual bucket count.

Here n is the number of input values. Output storage is not part of the extra-space bound.

Annotated solutionC++ · bucket minima and maxima · complete judge-ready method

CPPStore each bucket's extrema, then compare adjacent non-empty buckets.

#include <algorithm>
#include <climits>
#include <vector>

using namespace std;

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) return 0;

        int minVal = *min_element(nums.begin(), nums.end());
        int maxVal = *max_element(nums.begin(), nums.end());

        int bucketSize = max(1, (maxVal - minVal) / (n - 1));
        int bucketCount = (maxVal - minVal) / bucketSize + 1;

        vector<int> bucketMin(bucketCount, INT_MAX);
        vector<int> bucketMax(bucketCount, INT_MIN);

        for (int num : nums) {
            int index = (num - minVal) / bucketSize;
            bucketMin[index] = min(bucketMin[index], num);
            bucketMax[index] = max(bucketMax[index], num);
        }

        int answer = 0;
        int previousMax = minVal;

        for (int i = 0; i < bucketCount; ++i) {
            if (bucketMin[i] == INT_MAX) continue;

            answer = max(answer, bucketMin[i] - previousMax);
            previousMax = bucketMax[i];
        }

        return answer;
    }
};

The sentinel values make emptiness explicit: INT_MAX means no number has updated bucketMin yet, while INT_MIN safely initializes bucketMax. The scan carries only previousMax because the current bucket's minimum is the left endpoint of the gap from the preceding non-empty bucket. After that comparison, the current bucket's maximum becomes the only history needed for the next bucket.