Maximum Gap



@chubin said in Maximum Gap:
@leetcodeaccount it should be
(maxi  mini + bucketSize  1) / bucketSize
?On one hand, you're correct. On the other, your buckets number fails some tests (index out of range) but the wrong version survives.
That's where
⌈(max−min)/b⌉
sounds odd.

"Sorting an entire array can be costly. At worst, it requires comparing each element with every other element."
That's not exactly correct  it would mean that comparison based sort is inherently o(n^2), optimistic quadratic.
In optimal comparison based solutions a lot of comparisons are inferred by transitivity of order.

In the complexity analysis for the bucket approach, there are a number of $O(b)$ terms, but $b$ is defined above to be the size of the bucket. Shouldn't these terms refer to the number of buckets $k$?
If we let $m$ be the difference between the min and max element in the array, then $b \approx m/n$ and $k \approx m/b$, so $k \approx n$.

Hi LeetCoders,
Submitting my solution in python
class Solution(object):
def maximumGap(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
lenOfnums=len(nums)if(lenOfnums<2): return 0 nums.sort() maximumGap=0 for i in range(lenOfnums1): if(maximumGap < (nums[i+1]nums[i])): maximumGap=nums[i+1]nums[i] return maximumGap

@yolo
Think about a array like this {0, 1, 2, 3, 4, 50000}, we have total array.length  1 gaps.
So N  1 is the biggest number that we can use to ensure our solution's correctness(Pigeonhole principle).
you can definitely choose 1 or any number in the range [1, (max  min)/(n  1)] as your buckets size, in that case you have 50000 buckets, and you spend much more time on comparing buckets than directly sorting the array to get the results.
With N  1, you take O(n) time compare the buckets.