The problem
Return the maximum difference between successive elements of the SORTED form of an array — in linear time.
Stuck? Reveal hints one at a time
How to approach it
- 1Compute min and max; bucket width = max(1, ⌊(max − min) / (n − 1)⌋).
- 2Assign each number to bucket (v − min) / width, tracking only each bucket’s min and max.
- 3The answer gap must straddle buckets: scan buckets in order, measuring (current bucket min) − (previous non-empty bucket max).
- 4Return the largest such gap.
Key insight
The pigeonhole bound makes intra-bucket gaps provably too small — so you only need per-bucket extremes, never a sort.
The solution
Watch out for
- Empty buckets are the POINT — skip them but keep carrying previousMax forward.
- All-equal arrays divide by zero without the early min === max return.