Maximum Gap


  • 0

    Click here to see the full article post


  • 0
    L

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


  • 0
    A

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


  • 0
    L

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


  • 0
    A

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


  • 0
    L

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


  • 0
    _

    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)


  • 0
    J

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


  • 0
    Y

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

    why nums.size() - 1 ?


  • 0
    T

    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

  • 0
    S

    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.


  • 0
    Z

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


  • 0
    P

    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;
    }
    

    }


  • 0
    D

    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();


  • 0
    P

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


Log in to reply
 

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