Maximum Gap
Understanding the Problem
One way to solve this is to sort the array, then scan adjacent pairs to find the biggest gap. That works, but sorting takes O(n log n). The problem explicitly asks for O(n) time.
So the real question is whether we can find the maximum gap between successive elements in sorted order without sorting the entire array. We do not need a full sort. We only need enough information to identify which pair of successive elements produces the largest gap.
The Pigeonhole Principle gives us that information. If we spread n elements across n - 1 buckets of a certain width, at least one bucket must be empty. That empty bucket forces the maximum gap to span across buckets rather than fall within a single bucket. So we only need to track the min and max in each bucket, then scan bucket boundaries.
Key Constraints:
1 <= nums.length <= 10^5→ With n up to 100,000, an O(n log n) sorting approach would work in practice but violates the problem's O(n) requirement. We need a linear-time technique.0 <= nums[i] <= 10^9→ All values are non-negative. This simplifies bucket assignment since we do not need to handle negative number floor division. The range can be up to 10^9, so we cannot allocate an array of size equal to the value range. Bucket count must be proportional to n, not to the value range.
Approach 1: Sorting
Intuition
Sort the array, then compare every pair of adjacent elements. Once the array is sorted, the answer is max(nums[i+1] - nums[i]) over all valid i. This is correct, but it runs in O(n log n) time, which does not meet the problem's O(n) requirement. It still serves as a baseline and a sanity check for the linear-time approaches that follow.
Algorithm
- If the array has fewer than 2 elements, return 0.
- Sort the array in non-decreasing order.
- Initialize
maxGap = 0. - Iterate through the sorted array, computing the difference between each pair of adjacent elements.
- Update
maxGapwith the largest difference found. - Return
maxGap.
Example Walkthrough
Code
- Time Complexity: O(n log n). Sorting dominates. The subsequent linear scan is O(n), but the sort makes the overall complexity O(n log n).
- Space Complexity: O(1) to O(n). Depends on the sorting algorithm. In-place sorts use O(1), while Timsort uses O(n).
The bottleneck is comparison-based sorting, which cannot go below O(n log n). The full sorted order is more than we need. The next approach uses the Pigeonhole Principle to identify which pairs of elements can produce the maximum gap, in linear time, without sorting.
Approach 2: Bucket Sort (Pigeonhole Principle)
Intuition
Consider n elements ranging from min to max. If we spread n values evenly across this range, the average gap between successive elements is (max - min) / (n - 1). The maximum gap must be at least this average, because if every gap were smaller, the values could not span the full range from min to max.
Create buckets whose width equals this average gap, so each bucket covers a slice of the value range. Two elements in the same bucket differ by less than the bucket width, which is no larger than the average gap. Since the maximum gap is at least the average gap, it cannot come from two elements in the same bucket. It must span across buckets.
So there is no need to sort within buckets. For each bucket, we track only the minimum and maximum values. The maximum gap is then found by scanning 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.
Let g = floor((max - min) / (n - 1)) be the bucket width, and let G be the true maximum gap. The n values define n - 1 successive gaps that sum to max - min, so the largest of them satisfies G >= (max - min) / (n - 1) >= g. Any two values in the same bucket differ by at most g - 1, which is strictly less than G. The pair achieving G therefore lands in different buckets, so comparing the min of each non-empty bucket against the max of the previous non-empty bucket is enough to find it. Storing only the per-bucket min and max captures everything the scan needs.
Algorithm
- If the array has fewer than 2 elements, return 0.
- Find
minandmaxof the array. If they are equal, return 0. - Compute bucket width:
bucketSize = max(1, (max - min) / (n - 1)). - Compute the number of buckets:
bucketCount = (max - min) / bucketSize + 1. - For each bucket, maintain the minimum and maximum values.
- Place each element into its bucket:
bucketIndex = (nums[i] - min) / bucketSize. - Update the bucket's min and max.
- Scan through the buckets in order. For each non-empty bucket, compute the gap between its min and the max of the previous non-empty bucket.
- Return the maximum gap.
Example Walkthrough
Code
- Time Complexity: O(n). One pass to find min and max, one pass to place elements into buckets, one pass to scan buckets. All three passes are O(n).
- Space Complexity: O(n). We allocate three arrays (bucketMin, bucketMax, used) of size proportional to n.
The bucket approach is O(n) and meets the problem requirements. A different linear-time route fully sorts the array using radix sort, then scans adjacent pairs as in Approach 1.
Approach 3: Radix Sort
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 scan for the maximum gap as in Approach 1.
For this specific problem, radix sort does more work than the bucket method (it produces the full sorted order rather than only bucket boundaries), but it generalizes to any task that needs linear-time integer sorting.
Algorithm
- If the array has fewer than 2 elements, return 0.
- Find the maximum value to determine the number of digit passes needed.
- For each digit position (using base 10), perform counting sort on the current digit.
- After the array is fully sorted, scan adjacent pairs and return the maximum difference.
Example Walkthrough
Code
- Time Complexity: O(d * n) where d is the number of digits in the maximum value. For base 10 with values up to 10^9, d = 10. Since d is bounded by a constant, this is effectively O(n).
- Space Complexity: O(n). We need an auxiliary array of size n for the counting sort step, plus a count array of size 10 (constant).