Loading...
Loading...
Loading...
A company has delivery times in minutes. After sorting them, find the largest difference between two neighbouring times. Do it in O(n) time with buckets, not with a comparison sort.
Example 1
Input
3 6 9 1
Output
3
Example 2
Input
10 10
Output
0
Try the problem first. Open one hint at a time.
By the pigeonhole principle, the answer is at least (max - min) / (n - 1).
So the largest gap is never inside a bucket of that width: compare each bucket min with the previous bucket max.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor