#Idea: Radix sort, using buckets to store all intermediate numbers

#Time: O(10N) because 2^32 has ten digits, Space O(N)

class Solution(object):

def maximumGap(self, nums):

"""

:type nums: List[int]

:rtype: int

"""

if len(nums) < 2:

return 0

buckets = [[] for _ in range(10)]

maxi = max(nums)

i = 1 # i = 1, 10, 100, 1000....

while maxi // i > 0:

for num in nums:

digit = (num // i) % 10

buckets[digit].append(num)

nums = [num for bucket in buckets for num in bucket]

buckets = [[] for _ in range(10)]

i *= 10

max_gap = 0

i = 0

while i < len(nums) - 1:

max_gap = max(max_gap,nums[i+1]-nums[i])

i += 1

return max_gap