Given an unsorted array of non-negative integers, return the maximum difference between two successive elements in its sorted form, or 0 if it has fewer than two elements. Your algorithm must run in linear time and use linear extra space.
Before you code
A comparison sort is O(n log n), which the problem rules out. Two linear approaches work: radix sort the array, or use buckets cleverly so that you never need to sort inside a bucket.
Hints
- Radix sort: values are at most about 10⁹, so 4 passes of a byte-wise counting sort sort the array; then scan neighbors.
- Buckets: with n values between min and max, the maximum gap is at least (max − min)/(n − 1). Make buckets of that width. Two values in the same bucket are closer than that, so the answer is always between buckets.
- For each bucket keep only its min and max, then compare each bucket's min with the previous non-empty bucket's max.
Production & complexity notes
When solving Maximum gap on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Counting and radix sort to reinforce the underlying pattern.
What it practices
Sorting by value instead of by comparison, from Counting and radix sort.