162. Maximum Gap
You are given an unsorted array nums of non-negative integers. Imagine the array arranged in ascending order, and look at the differences between every pair of neighboring elements in that order. Return the largest such difference.
If the array holds fewer than two elements, return 0.
Sorting first is the easy route — the real challenge is to answer in linear time and linear space, without ever fully sorting the array.
Example 1:
Input: nums = [3, 6, 9, 1]
Output: 3
Explanation: Sorted, the array reads [1, 3, 6, 9]. The neighbor differences are 2, 3, and 3, so the largest gap is 3.
Example 2:
Input: nums = [10]
Output: 0
Explanation: With a single element there are no neighboring pairs, so the answer defaults to 0.
Constraints:
- 1 ≤ nums.length ≤ 10⁵
- 0 ≤ nums[i] ≤ 10⁹
Hints:
Sort-then-scan is a valid warm-up: after sorting, one pass over adjacent pairs finds the answer in O(n log n).
Pigeonhole: with n values spread between min and max, the largest gap is at least ceil((max − min) / (n − 1)). Split the value range into buckets slightly narrower than that bound — then no two values in the SAME bucket can form the maximum gap.
Because the answer never lives inside a bucket, you only need each bucket's min and max. Walk the non-empty buckets in order and measure current bucket's min minus the previous bucket's max.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [3, 6, 9, 1]
Expected output: 3