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.


Log in to reply
 

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