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.


Log in to reply
 

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