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.

Help needed !!!
I translated the third solution (pigeonhole) into Java but it wouldn't work.
I keep getting java.lang.NullPointerException error when the code is trying to modify the fields(used, minval, maxval) of a bucket (Please see my comments in the code). The buckets are properly initialized using defined constructor. Why are they null? So confused.Any help will be appreciated!!
public class Solution
{public class Bucket { public Boolean used; public int minval; public int maxval; public Bucket() { used = false; minval = Integer.MAX_VALUE; maxval = Integer.MIN_VALUE; } } public int maximumGap(int[] nums) { if (nums == null  nums.length < 2) return 0; //find min and max element in nums[] int mini = nums[0]; int maxi = nums[0]; for(int i:nums) { maxi = Math.max(maxi,i); mini = Math.min(mini,i); } //Allocate buckets int bucketSize = Math.max(1, (maxi  mini) / (nums.length  1)); int bucketNum = (maxi  mini) / bucketSize + 1; Bucket[] buckets = new Bucket[bucketNum]; for (Bucket b : buckets) b = new Bucket(); for (int i : nums) { int bucketIdx = (i  mini) / bucketSize; buckets[bucketIdx].used = true; //Error occurs here when trying to access a field of a bucket buckets[bucketIdx].minval = Math.min(i, buckets[bucketIdx].minval); //Same error would occur here buckets[bucketIdx].maxval = Math.max(i, buckets[bucketIdx].maxval); //Same error would occur here } int maxGap = 0; int prevBucketMax = mini; for (Bucket b : buckets) { if (!b.used) continue; maxGap = Math.max(maxGap, b.minval  prevBucketMax); prevBucketMax = b.maxval; } return maxGap; }
}

Fantastic explanation of applying the buckets.
@pat1012 I hope you've figured out your error by now, but if not may want to look at this section:
Bucket[] buckets = new Bucket[bucketNum];
for (Bucket b : buckets)
b = new Bucket();

@dkimandersen Thank you for replying.
I know manually initializing each bucket in the array is unnecessary.
So I deleted these two lines:
for (Bucket b : buckets)
b = new Bucket();But it still won't work.
Any idea?