DSA problem
Maximum Gap
Given an integer array nums, return the maximum difference between two successive elements in its sorted form. If the array contains less than two elements, return 0. You must write an algorithm that runs in linear time and uses linear extra space.
The trivial solution sorts the array and scans neighboring pairs, but that costs O(n log n) and violates the constraint. To achieve linear time you must avoid any general comparison sort.
The key insight is pigeonhole bucketing. Suppose nums has n elements with minimum minV and maximum maxV. After sorting, the n - 1 consecutive gaps sum to maxV - minV, so by the pigeonhole principle the maximum gap is at least ceil((maxV - minV) / (n - 1)). Choose this value as the bucket size. Two numbers that fall into the same bucket therefore differ by strictly less than the bucket size, which means the answer cannot be a within-bucket difference — it must be a between-bucket difference.
Allocate n buckets indexed by (num - minV) / bucketSize. For each bucket store only its current minimum and maximum (no need to store every element). Then scan the buckets in order, tracking the maximum of the previous non-empty bucket; the gap is bucket.min - prevMax. Update prevMax to the current bucket's maximum and continue. The total work is O(n) time and O(n) space — exactly what the problem demands.
Examples
nums = [3,6,9,1]3nums = [10]0nums = [1,10000000]9999999Constraints
- 1 <= nums.length <= 10^5
- 0 <= nums[i] <= 10^9
- Your algorithm must run in O(n) time and use O(n) extra space.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.