# [Memory Limit Exceeded]My Python Code got a MLE

• ``````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``````

• 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``````

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

• Thanks a lot! Your fix worked! :D

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

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

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

• Yes, u r right. I made a mistake.

• 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()?

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

• 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)``````

• 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

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