# Maximum Gap

• Could you explain why the buckets number `(maxi - mini) / bucketSize + 1` and `⌈(max−min)/b⌉` are the same thing?

• @leetcodeaccount it should be `(maxi - mini + bucketSize - 1) / bucketSize`?

• @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.

• For array of non-negative integers, the function should return `(maxi - mini)` immediately if it is not greater than 1.

• "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.

• Is it normal to not even mention the complexity cost of min/max element finding? in the bucket solution the min/max finding the O(n) of min and max is often more relevant than the b term in O(n+b)

• 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\$.

• Why are we setting bucket size as
int bucketSize = max(1, (maxi - mini) / ((int)nums.size() - 1))>

why nums.size() - 1 ?

• 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(lenOfnums-1):

if(maximumGap < (nums[i+1]-nums[i])):
maximumGap=nums[i+1]-nums[i]

return maximumGap``````

• Solution with bucketing: factor 'b' is not linear to 'n' because (max-min) can be arbitrarily large. Scanning all such buckets is not linear to n.

• @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?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.