# Python solution with detailed explanation

• Solution

1. The first algorithm is to sort the numbers using radix-sort. We use the algorithm for sorting constant width strings moving from least significant to most significant digit. For example, sorting 334, 146, 192:
• First sort by the units digits (4, 6, 2): 192, 334, 146
• Sort by tens digit (9,3,4): 334, 146, 192
• Sort by hundreds digit (3,1,1): 146, 192, 334
2: How do we determine width of these integers? width = len(str(2^31-1))-1
``````from collections import defaultdict
class Solution(object):
q = 1
for w in range(width):
q = q*10 if w > 0 else 1
num_dict = defaultdict(list)
for x in nums:
digit = (x // q) % 10
num_dict[digit].append(x)
i = 0
for k in range(10):
for x in num_dict[k]:
nums[i], i = x, i+1
return

def maximumGap(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
width = len(str(2**31-1))-1
max_gap = 0
for i in range(1, len(nums)):
max_gap = max(nums[i] - nums[i-1], max_gap)
return max_gap
``````

• Alternative implementation for Radix Sort as given by Sedgewick.
``````class Solution(object):
q = 1
for w in range(width):
q = q*10 if w > 0 else 1
# Get the frequency of each alphabet
for x in nums:
digit = (x // q) % 10
# Build the cumulative array. This array tells us
# the starting position for every character in the temp array.
for i in range(1,11):
temp = [None]*len(nums)
for x in nums:
digit = (x // q) % 10
for i in range(len(temp)):
nums[i] = temp[i]
return

def maximumGap(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
width = len(str(2**31-1))-1
max_gap = 0
for i in range(1, len(nums)):
max_gap = max(nums[i] - nums[i-1], max_gap)
return max_gap
``````

Bucket Sort
The bucket sort algorithm is explained with comments. https://discuss.leetcode.com/topic/5999/bucket-sort-java-solution-with-explanation-o-n-time-and-space/2

``````class Solution(object):
def maximumGap(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
N = len(nums)
if N < 2:
return 0
min_n, max_n = min(nums), max(nums)
gap = int(ceil((max_n-min_n)/float(N-1)))
buckets = [[None, None] for _ in range(N-1)]
for x in nums:
if x == max_n:
continue
slot = int((x-min_n)/gap)
buckets[slot][0] = min(buckets[slot][0], x) if buckets[slot][0] else x
buckets[slot][1] = max(buckets[slot][1], x) if buckets[slot][1] else x
max_gap, prev_max = gap, buckets[0][1]
for b in buckets:
if b[0] == None and b[1] == None:
continue
else:
max_gap = max(max_gap, b[0]-prev_max)
prev_max = b[1]
if prev_max:
max_gap = max(max_gap, max_n-prev_max)
return max_gap
``````

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