# Simple radix sort solution in python

• ``````class Solution:
# @param {integer[]} nums
# @return {integer}
for k in xrange(10):
s=[[] for i in xrange(10)]
for i in A:
s[i/(10**k)%10].append(i)
A=[a for b in s for a in b]
return A

def maximumGap(self, nums):
ans = 0
if len(A) == 0: return 0
prev = A[0]
for i in A:
if i - prev > ans: ans = i - prev
prev = i
return ans``````

• not in constant space right?

• linear space/time

• Similar idea and code

``````class Solution(object):
def maximumGap(self, nums):
for _ in range(10):
bus=[[] for _ in range(10)]
for n in nums:
nums=reduce(lambda x,y: x+y, bus)
for i, n in enumerate(nums[1:]):
maxg=max(n-nums[i], maxg)
return maxg``````

• @AceSmg not very understandable code. Check this out:

``````class Solution(object):
def maximumGap(self, nums):
idx, bits = 0, 32
while idx < bits:
zeroes, ones = [], []
for num in nums:
if num & (1 << idx):
ones.append(num)
else: zeroes.append(num)
nums = zeroes + ones
idx += 1
return nums

For example, chosing `a = [4, 9, 2, 6, 8, 1]` results in `maximumGap(a) = 2`. The right solution in this case would be `4 - 0 = 4`, since `a[4] = 8 < a[0] = 0`.