Maximum gap between sorted neighbors in linear time

Given an unsorted array of non-negative integers, return the largest difference between two neighbours once the array is sorted. Return 0 if there are fewer than two elements. Run in O(n) time and O(n) extra space, without a comparison sort.

Interface

Unless you agree on a different interface with the interviewer, assume:

• maximum_gap(nums: list[int]) -> int

Example

maximum_gap([3, 6, 9, 1])     ->  3    # sorted: 1 3 6 9, gaps 2 3 3
maximum_gap([10])             ->  0
maximum_gap([1, 1, 1])        ->  0
maximum_gap([1, 10000000])    ->  9999999

Constraints

• 1 <= len(nums) <= 10^5, 0 <= nums[i] <= 10^9.

Clarifying questions

• Can values repeat or be negative?
• What is returned for fewer than two elements?
• Is a comparison sort really not allowed?

What a strong answer covers

• Pigeonhole: with n numbers between lo and hi, the maximum gap is at least ceil((hi - lo) / (n - 1)); use buckets of that width (at least 1).
• Each bucket stores only its min and max; the answer is the largest next bucket's min - previous non-empty bucket's max, since no gap inside a bucket can be the maximum.
• Edge cases: all values equal, two elements, empty buckets between.
• O(n) time and space; radix sort as the alternative linear method, with its trade-offs.

Follow-ups

• Values can be negative or floats.
• Return the pair of values that forms the gap.
• The numbers arrive as a stream that can't be stored.