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.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Sorting

Data structures

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

Solutions:
class Solution:

	def maximumGap(self, nums):
		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):
		nums.sort()
		try:
			return max(list(map(lambda i, j: j - i, nums, nums[1:])))
		except:
			return 0


class Solution:

	def maximumGap(self, nums):
		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):
		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)
		n = (maxV - minV) // n_size + 1
		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):
		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):
		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):
		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):
		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']
		return max_diff


class Solution:

	def maximumGap(self, nums):
		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