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