Maximum Gap

Problem

Monitoring systems alert on the widest quiet stretch between sensor readings: given the sorted order of a set of integers, the gap is the largest difference between consecutive values. Given an unsorted array, find that maximum gap in linear time - without sorting the values against each other.

Example 1:

Input: nums = [9, 37, 4]
Output: 28
Explanation: sorted, the values are [4, 9, 37]; the widest consecutive gap is 37 - 9 = 28.

Example 2:

Input: nums = [6, 6, 6]
Output: 0
Explanation: identical values have no gaps at all.

Example 3:

Input: nums = [1, 10000000]
Output: 9999999
Explanation: two values, one enormous gap between them.

Constraints:

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^9

Solution Breakdown

Approach - range-bucketing with a pigeonhole proof that the answer never hides inside a bucket.

Comparison sorting has an O(n log n) floor, so the linear bound must come from the value structure: n integers spanning [lo, hi] have an average consecutive gap of (hi - lo) / (n - 1). Cut the range into buckets of width max(1, (hi - lo) // (n - 1)) - the floored average, never zero. The pigeonhole argument: within one bucket, two consecutive sorted values differ by at most bucket_size - 1, which is at most the floored average; if every bucket were packed, the maximum gap would be no larger than that average - and whenever the true maximum gap exceeds the average, some bucket must be empty, which forces the gap to open across a bucket boundary. Either way, the winning difference is between the maximum of one non-empty bucket and the minimum of the next non-empty bucket, so buckets only need to store their min and max - never their contents.

Fill in one pass (idx = (num - lo) // bucket_size, the +1 in bucket_count keeping hi's index in range), then sweep non-empty buckets in order with prev_max initialized to lo: each candidate is bucket_min[i] - prev_max, and prev_max becomes bucket_max[i]. Trace [9, 37, 4]: lo 4, hi 37, n 3 - size 16, buckets 0..2; bucket 0 holds (4, 9), bucket 1 is empty, bucket 2 holds (37, 37). The sweep: candidate 4 - 4 = 0, then skip the empty, then 37 - 9 = 28 - the answer, matching the sorted scan [4, 9, 37].

Edge cases - fewer than two elements return 0 (no pair to gap); all-equal values short-circuit on lo == hi before bucketing; a two-element input degenerates to one giant bucket pair where the boundary gap is the whole spread ([1, 10000000] -> 9999999).

Complexity - O(n) time: one min/max scan, one bucket-fill pass at O(1) per element, one sweep over at most n + 1 buckets (bucket_size >= floored average caps the count; the max(1, ...) guard keeps tiny ranges linear too). O(n) space for the two bucket arrays. Radix sort also meets the linear bound, but bucketing never sorts at all - the pigeonhole proof does the work.