At first glance, this looks straightforward: sort the array, then scan adjacent pairs to find the biggest gap. And that works, but sorting takes O(n log n). The problem explicitly asks for O(n) time.

So the real question is: can we find the maximum gap between successive elements in sorted order without actually sorting the entire array? This is where it gets interesting, because it turns out we do not need a full sort. We just need enough information to identify which pair of successive elements produces the largest gap.

The key insight comes from the Pigeonhole Principle. If we spread n elements across n - 1 buckets of a certain width, at least one bucket must be empty. That empty bucket guarantees the maximum gap spans across buckets, not within a single bucket. So we only need to track the min and max in each bucket, then scan bucket boundaries.

Key Constraints:

Intuition

The simplest approach is to sort the array and then compare every pair of adjacent elements. The largest difference among those pairs is the answer. This is the first thing anyone would think of, and it is correct. The only issue is that it runs in O(n log n) time, which does not meet the problem's requirement of O(n).

Still, it is a great starting point because it makes the problem concrete: once sorted, the answer is just max(nums[i+1] - nums[i]) for all valid i.

Algorithm

Example Walkthrough

Code

The bottleneck here is comparison-based sorting, which cannot go below O(n log n). But we do not actually need the full sorted order. We only need to know which pairs of elements are adjacent in sorted order. What if we could figure out which pairs matter without sorting everything?

Intuition

Here is the key insight that makes this problem beautiful. Suppose we have n elements ranging from min to max. If we spread n values evenly across this range, the average gap between successive elements would be (max - min) / (n - 1). The maximum gap must be at least this average, because if every gap were smaller, the total range would be less than max - min.

Now, imagine we create buckets of width equal to this average gap. Each bucket covers a slice of the value range. Here is the trick: since the bucket width equals the minimum possible maximum gap, the maximum gap can never occur between two elements in the same bucket. Two elements in the same bucket differ by less than the bucket width, which is at most the average gap. The maximum gap must be at least the average gap. So the maximum gap must span across buckets.

This means we do not need to sort within buckets at all. For each bucket, we only need to track the minimum and maximum values. Then the maximum gap is found by scanning through the buckets in order and computing the difference between the min of the current non-empty bucket and the max of the previous non-empty bucket.

Algorithm

Example Walkthrough

Code

The bucket approach is already O(n) and meets the problem requirements. But there is an alternative O(n) approach using radix sort that fully sorts the array in linear time, which is worth understanding as a more general technique.

Intuition

Radix sort is a non-comparison-based sorting algorithm that sorts integers digit by digit, from the least significant digit to the most significant. For each digit position, it uses counting sort as a subroutine, which is O(n + k) where k is the range of a single digit (0-9 for base 10).

Since all values are non-negative integers up to 10^9, radix sort with base 10 processes up to 10 digit positions and makes 10 passes through the array. Each pass is O(n), so the total is O(10n) = O(n). After radix sort, the array is fully sorted, and we can scan for the maximum gap just like in Approach 1.

This approach is less elegant than buckets for this specific problem, but it is a valuable tool to know. Radix sort is the standard answer when someone asks "how do you sort in O(n)?" in an interview context.

Algorithm

Example Walkthrough

Code