[Memory Limit Exceeded]My Python Code got a MLE


  • 0
    class Solution:
    # @param num, a list of integer
    # @return an integer
    def maximumGap(self, num):
        N = len(num)
        if N < 2:
            return 0
        A = min(num)
        B = max(num)
        bucketLen = int(0.5 + 1.0 * (B - A) / (N - 1)) #ceil( (B - A) / (N - 1) )
        buckets = {}
        for K in num:
            loc = (K - A) / bucketLen
            bucket = buckets.get(loc)
            if bucket is None:
                bucket = {'min' : K, 'max' : K}
                buckets[loc] = bucket
            else:
                bucket['min'] = min(bucket['min'], K)
                bucket['max'] = max(bucket['max'], K)
        maxGap = 0
        for x in range(bucketLen):
            if buckets.get(x) is None:
                continue
            y = x + 1
            while y < bucketLen and buckets.get(y) is None:
                y += 1
            if y < bucketLen:
                maxGap = max(maxGap, buckets[y]['min'] - buckets[x]['max'])
            x = y
        return maxGap

  • 2
    J

    Use array instead of dict, then pass. Don't know why. Maybe the keys take much space for iterating.

    class Solution:
        def maximumGap(self, num):
            N = len(num)
            if (N < 2):
                return 0
            imin = min(num)
            imax = max(num)
            M = max(1, int(0.5 + 1.0 * (imax - imin) / (N - 1)))
            buckets = [None] * ((imax - imin) / M + 1)
            for x in num:
                i = (x - imin) / M
                bucket = buckets[i]
                if bucket is None:
                    buckets[i] = {'min': x, 'max': x}
                else:
                    bucket['min'] = min(bucket['min'], x)
                    bucket['max'] = max(bucket['max'], x)
            gap = 0
            prev = buckets[0]
            for i in range(1, len(buckets)):
                if buckets[i] is None:
                    continue
                gap = max(gap, buckets[i]['min'] - prev['max'])
                prev = buckets[i]
            return gap

  • 0
    J

    Please note that bucketLen may be 0, which will cause ZeroDivisionError.


  • 0

    Thanks a lot! Your fix worked! :D


  • 0
    J

    PS: ceil(x) is not the equivalent of int(0.5 + x), but in this solution, any positive integer K < ceil( (imax - imin) / (N - 1) ) is ok, since the different of any two numbers in the same bucket is smaller than the minimal gap.


  • 0

    I see...
    Do you mean ceil(x) = int(0.5 + x) only when x >= 0;
    Is that correct?


  • 0
    J

    For both negatives and non-negatives, only when round(x + 0.5) > x and round(x + 0.5) != x+1 will int(x + 0.5) = ceil(x).


  • 0

    Yes, u r right. I made a mistake.


  • 0

    b.t.w. Could you please share your original python solution here? It seems that import math is not permitted and will get a Compile Error after submitting my code. Or do you have a quick solution to replace the function math.ceil()?


  • 0

    Maybe this works... ceil( A / B) = int( (A - 1) / B + 1) when A, B are both integers.


  • 0
    J

    Emmm. It seems true if B = 1 or (A >= 0 and B > 0). It is sufficient for this algorithm.

    My solution is:

    def ceil(x):
        y = x % 1
        return int(y == 0 and x or x - y + 1)

  • 0
    J

    Oh, please ignore my ceil function above, it is buggy…should be:

    def ceil(x):
        y = x % 1
        if y == 0:
            return int(x)
        return int(x - y + 1)
    

    Still a little buggy, ceil(1/1e309) yield 0, ceil(3.0000000000000001) yield 3. But its behavior is similar to math.ceil


Log in to reply
 

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