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
[Memory Limit Exceeded]My Python Code got a MLE


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