Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Return 0 if the array contains less than 2 elements.

Example 1:


Input: [3,6,9,1]
Output: 3
Explanation: The sorted form of the array is [1,3,6,9], either
             (3,6) or (6,9) has the maximum difference 3.

Example 2:


Input: [10]
Output: 0
Explanation: The array contains less than 2 elements, therefore return 0.

Note:


       You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.
       Try to solve it in linear time/space.

Difficulty: interview

Starter code:

class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        

Solutions:
class Solution:
     def maximumGap(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if not nums or len(nums) == 1:
             return 0
         sorted_gap=0
         nums=list(set(nums))
         nums.sort()
         for curr in range(len(nums[:-1])):
             gap=nums[curr+1]-nums[curr]
             if gap>sorted_gap:
                 sorted_gap=gap
         
         return sorted_gap

class Solution:
     def maximumGap(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         nums.sort()
         try:
             return(max(list(map(lambda i,j:j-i,nums,nums[1:]))))
         except: return(0)

class Solution:
     def maximumGap(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if len(nums) < 2:
             return 0
 
         if len(nums) == 2:
             return abs(nums[0] - nums[1])
 
         left, right = min(nums), max(nums)
         brng = (right - left) // (len(nums) - 1) + 1
         bnum = (right - left) // brng + 1
         bucket = [None] * bnum
         for x in nums:
             idx = (x - left) // brng
             if bucket[idx]:
                 bucket[idx] = (min(bucket[idx][0], x), max(bucket[idx][1], x))
             else:
                 bucket[idx] = (x, x)
 
         max_gap = pre = 0
         for cur in range(1, bnum):
             if not bucket[cur]:
                 continue
             max_gap = max(max_gap, bucket[cur][0] - bucket[pre][1])
             pre = cur
 
         return max_gap

class Solution:
     def maximumGap(self, num):
         if len(num) < 2 or min(num) == max(num):
             return 0
         a, b = min(num), max(num)
         import math
         size = math.ceil((b - a) / (len(num) - 1))
         bucket = [[None, None] for _ in range((b - a) // size + 1)]
         for n in num:
             b = bucket[(n - a) // size]
             b[0] = n if b[0] is None else min(b[0], n)
             b[1] = n if b[1] is None else max(b[1], n)
         bucket = [b for b in bucket if b[0] is not None]
         return max(bucket[i][0] - bucket[i - 1][1] for i in range(1, len(bucket)))

class Solution:
     def maximumGap(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         nums.sort()
         try:
             return(max(list(map(lambda i,j:j-i,nums,nums[1:]))))
         except: return(0)

class Solution:
     def maximumGap(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if len(nums)<2:
             return 0
         minV = nums[0]
         maxV = nums[0]
         for i in range(len(nums)):
             if nums[i]<minV:
                 minV = nums[i]
             if nums[i]>maxV:
                 maxV = nums[i]
         
         l = len(nums)
         n_size = max((maxV-minV)//(l-1),1)
         #print(n_size)
         n = (maxV-minV)//n_size+1
         #print(n)
         #return 0
         if n==1:
             return maxV-minV
         
         b_max = [minV]*n
         b_min = [maxV]*n
         b_count = [0]*n
         
         for i in range(l):
             b_id = (nums[i]-minV)//n_size
             b_count[b_id]+=1
             if nums[i]>b_max[b_id]:
                 b_max[b_id] = nums[i]
             if nums[i]<b_min[b_id]:
                 b_min[b_id] = nums[i]
         
         last_max = minV
         maxGap = 1
         for i in range(n):
             if b_count[i]>0:
                 maxGap = max(maxGap,b_min[i]-last_max)
                 last_max  = b_max[i]
         
         return maxGap
                 
         


class Solution(object):
     def maximumGap(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if(len(nums) == 0):
             return 0
         Max, Min = max(nums), min(nums)
         if(Max == Min):
             return 0
         if(len(nums) == 2):
             return Max-Min
         import math
         nums = list(set(nums))
         Len = int(math.ceil((Max-Min)/(len(nums)-1)))
         print(Max,Min)
         print((Max-Min)/(len(nums)-1))
         Count = (Max-Min)//Len + 1
         List = [[] for i in range(Count)]
         
         Gap = 0
         for i in nums:
             ilen = int((i-Min)//Len)
             
             List[ilen].append(i)
             
         mmin = max(List[0])
         for i in range(1,Count):
             if(List[i] != []):
                 Gap = max(Gap, min(List[i])-mmin)
                 mmin = max(List[i])
         return Gap    

class Solution:
     def maximumGap(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         import math,sys
         if not nums or len(nums)<2: 
             return 0
 
         lenn = len(nums)
         maxx = nums[0]
         minn = nums[0]
         for i in range(len(nums)):
             maxx = max(maxx, nums[i])
             minn = min(minn, nums[i])
 
         gap = math.ceil((maxx-minn)/(lenn-1))
         bucketsMin = [2**31-1]*(lenn-1)
         bucketsMax = [-2**31+1]*(lenn-1)
         for num in nums:
             if num==minn or num==maxx:
                 continue
             bucket = (num-minn)//gap
             bucketsMin[bucket]=min(num, bucketsMin[bucket])
             bucketsMax[bucket]=max(num, bucketsMax[bucket])
         res = 0
         pre = minn 
         for i in range(lenn-1):
             if bucketsMin[i]==(2**31-1) and bucketsMax[i]==(-2**31+1):
                 continue
             res = max(res, bucketsMin[i] - pre)
             pre = bucketsMax[i]
 
         res = max(res, maxx-pre)
         return res

class Solution:
     def maximumGap(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if len(nums)<2:
             return 0
         a = nums[0]
         b = nums[0]
         for num in nums:
             a = min(a, num)
             b = max(b, num)
             
         bucketSize = max(1, (b-a)//(len(nums)-1))
         bucketNum = (b-a)//bucketSize + 1
         buckets = [[-1, -1] for i in range(bucketNum)]
         for num in nums:
             locate = (num-a)//bucketSize
             if buckets[locate][0] == -1:
                 buckets[locate][0] = num
                 buckets[locate][1] = num
             else:
                 buckets[locate][0] = min(num, buckets[locate][0])
                 buckets[locate][1] = max(num, buckets[locate][1])
         maxGap = 0
         pre = a
         for bucket in buckets:
             if bucket[0] == -1:
                 continue
             maxGap = max(maxGap, bucket[0] - pre)
             pre = bucket[1]
         return maxGap

class Solution:
     def maximumGap(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         n = len(nums)
         if n == 0:
             return 0
         buckets = [{"min": None, "max": None} for _ in range(n)]
         n_min = min(nums)
         n_max = max(nums)
         if n_max == n_min:
             return 0
         for num in nums:
             i = (num - n_min) * (n - 1) // (n_max - n_min)
             if buckets[i]["min"] is None:
                 buckets[i]["min"] = num
                 buckets[i]["max"] = num
             else:
                 buckets[i]["min"] = min(num, buckets[i]["min"])
                 buckets[i]["max"] = max(num, buckets[i]["max"])
         max_diff = 0
         max_prev = buckets[0]["max"]
         for i in range(1, n):
             if buckets[i]["min"] is not None:
                 max_diff = max(max_diff, buckets[i]["min"]-max_prev)
                 max_prev = buckets[i]["max"]
         #print(buckets)
         return max_diff

class Solution:
     def maximumGap(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if len(nums)<2:
             return 0
         
         m = 0
         for num in nums:
             m = max(m, num)
         
         exp = 1
         while m//exp:
             aux = [[] for i in range(10)]
             for num in nums:
                 aux[(num//exp)%10].append(num)
             index = 0
             for item in aux:
                 if len(item)!=0:
                     for i in item:
                         nums[index] = i
                         index += 1
             exp *= 10
         
         maxGap = 0
         pre = nums[0]
         for num in nums:
             maxGap = max(maxGap, num - pre)
             pre = num
         return maxGap