# Question

Formatted question description: https://leetcode.ca/all/164.html

Given an integer array nums, return the maximum difference between two successive elements in its sorted form. If the array contains less than two elements, return 0.

You must write an algorithm that runs in linear time and uses linear extra space.

Example 1:

Input: nums = [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: nums = [10]
Output: 0
Explanation: The array contains less than 2 elements, therefore return 0.


Constraints:

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 109

# Algorithm

Bucket Sort is employed here. Initially, identify the maximum and minimum values within the array. Subsequently, calculate the capacity of each bucket, which is determined by (maximum - minimum) / number + 1. To ascertain the required number of buckets, compute (maximum - minimum) / capacity of a bucket + 1.

Next, it’s essential to identify the local maximum and minimum within each bucket. Notably, the two numbers exhibiting the greatest distance will not reside within the same bucket. Instead, such a distance is observed between the minimum value of one bucket and the maximum value of another bucket. This observation is grounded in the principle that all numbers should be distributed across the buckets as evenly as possible, rather than clustering within a single bucket. This distribution strategy ensures that the maximum and minimum values are unlikely to be found in the same bucket.

# Code

• 
public class Maximum_Gap {

public class Solution {
public int maximumGap(int[] nums) {
if (nums == null || nums.length <= 1) {
return 0;
}

// Step 1: find max and min element
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int num : nums) {
if (num > max) {
max = num;
}

if (num < min) {
min = num;
}
}

int len = nums.length;

// Step 2: calculate the intervals and number of buckets.
int interval = (int) Math.ceil((double) (max - min) / (len - 1));

if (interval == 0) {
interval = 1;
}
int numBuckets = (max - min) / interval + 1;
Bucket[] buckets = new Bucket[numBuckets];
for (int i = 0; i < numBuckets; i++) {
buckets[i] = new Bucket();
}

// Step 3: iterate through the nums and assign the number into the buckets.
for (int num : nums) {
int bucketNum = (num - min) / interval;
if (num > buckets[bucketNum].max) {
buckets[bucketNum].max = num;
}

if (num < buckets[bucketNum].min) {
buckets[bucketNum].min = num;
}
}

// Step 4: iterate through the buckets and get the maximal gap
int prev = buckets[0].max;
int maxGap = 0;
for (int i = 1; i < numBuckets; i++) {
if (prev != Integer.MIN_VALUE && buckets[i].min != Integer.MAX_VALUE) {
maxGap = Math.max(maxGap, buckets[i].min - prev);
prev = buckets[i].max;
}
}

return maxGap;
}

private class Bucket {
public int min;
public int max;

public Bucket() {
min = Integer.MAX_VALUE;
max = Integer.MIN_VALUE;
}
}
}

}

//////

class Solution {
public int maximumGap(int[] nums) {
int n = nums.length;
if (n < 2) {
return 0;
}
int inf = 0x3f3f3f3f;
int mi = inf, mx = -inf;
for (int v : nums) {
mi = Math.min(mi, v);
mx = Math.max(mx, v);
}
int bucketSize = Math.max(1, (mx - mi) / (n - 1));
int bucketCount = (mx - mi) / bucketSize + 1;
int[][] buckets = new int[bucketCount][2];
for (var bucket : buckets) {
bucket[0] = inf;
bucket[1] = -inf;
}
for (int v : nums) {
int i = (v - mi) / bucketSize;
buckets[i][0] = Math.min(buckets[i][0], v);
buckets[i][1] = Math.max(buckets[i][1], v);
}
int prev = inf;
int ans = 0;
for (var bucket : buckets) {
if (bucket[0] > bucket[1]) {
continue;
}
ans = Math.max(ans, bucket[0] - prev);
prev = bucket[1];
}
return ans;
}
}

• // OJ: https://leetcode.com/problems/maximum-gap/
// Time: O(N)
// Space: O(N)
// Ref: https://discuss.leetcode.com/topic/5999/bucket-sort-java-solution-with-explanation-o-n-time-and-space
class Solution {
public:
int maximumGap(vector<int>& A) {
if (A.size() == 1) return 0;
int minVal = *min_element(begin(A), end(A));
int maxVal = *max_element(begin(A), end(A));
int N = A.size(), gap = (maxVal - minVal + N - 2) / (N - 1);
vector<int> mn(N - 1, INT_MAX), mx(N - 1, INT_MIN);
for (int n : A) {
if (n == minVal || n == maxVal) continue;
int i = (n - minVal) / gap;
mn[i] = min(mn[i], n);
mx[i] = max(mx[i], n);
}
int ans = gap, prev = minVal;
for (int i = 0; i < N - 1; ++i) {
if (mn[i] == INT_MAX) continue;
ans = max(ans, mn[i] - prev);
prev = mx[i];
}
return max(ans, maxVal - prev);
}
};

• '''
>>> math.inf
inf
>>> 1 + math.inf
inf
>>> -1 - math.inf
-inf
'''
class Solution:
def maximumGap(self, nums: List[int]) -> int:
n = len(nums)
if n < 2:
return 0
mi, mx = min(nums), max(nums)
# also passing OJ:
# bucket_size = max(1, (mx - mi) // (n - 1))
bucket_size = max(1, (mx - mi) // n)
bucket_count = (mx - mi) // bucket_size + 1
buckets = [[inf, -inf] for _ in range(bucket_count)]
for v in nums:
i = (v - mi) // bucket_size
buckets[i][0] = min(buckets[i][0], v)
buckets[i][1] = max(buckets[i][1], v)
ans = 0
prev = inf
for curmin, curmax in buckets:
if curmin > curmax:
continue
ans = max(ans, curmin - prev)
prev = curmax
return ans

############

class Solution(object):
def maximumGap(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) < 2:
return 0
a, b = min(nums), max(nums)
if a == b:
return 0
ans = 0
gap = int(math.ceil((b - a + 0.0) / (len(nums) - 1)))
bucketMin = [None for _ in range(0, len(nums) + 1)]
bucketMax = [None for _ in range(0, len(nums) + 1)]

for num in nums:
index = (num - a) / gap
if bucketMin[index] is None:
bucketMin[index] = num
else:
bucketMin[index] = min(bucketMin[index], num)
if bucketMax[index] is None:
bucketMax[index] = num
else:
bucketMax[index] = max(bucketMax[index], num)
bucketMin = [b for b in bucketMin if b is not None]
bucketMax = [b for b in bucketMax if b is not None]
for i in range(0, len(bucketMin) - 1):
ans = max(ans, bucketMin[i + 1] - bucketMax[i])
return ans


• func maximumGap(nums []int) int {
n := len(nums)
if n < 2 {
return 0
}
inf := 0x3f3f3f3f
mi, mx := inf, -inf
for _, v := range nums {
mi = min(mi, v)
mx = max(mx, v)
}
bucketSize := max(1, (mx-mi)/(n-1))
bucketCount := (mx-mi)/bucketSize + 1
buckets := make([][]int, bucketCount)
for i := range buckets {
buckets[i] = []int{inf, -inf}
}
for _, v := range nums {
i := (v - mi) / bucketSize
buckets[i][0] = min(buckets[i][0], v)
buckets[i][1] = max(buckets[i][1], v)
}
ans := 0
prev := inf
for _, bucket := range buckets {
if bucket[0] > bucket[1] {
continue
}
ans = max(ans, bucket[0]-prev)
prev = bucket[1]
}
return ans
}

func min(a, b int) int {
if a < b {
return a
}
return b
}

func max(a, b int) int {
if a > b {
return a
}
return b
}

• using System;
using System.Linq;

public class Solution {
public int MaximumGap(int[] nums) {
if (nums.Length < 2) return 0;
var max = nums.Max();
var min = nums.Min();
var bucketSize = Math.Max(1, (max - min) / (nums.Length - 1));
var buckets = new Tuple<int, int>[(max - min) / bucketSize + 1];
foreach (var num in nums)
{
var index = (num - min) / bucketSize;
if (buckets[index] == null)
{
buckets[index] = Tuple.Create(num, num);
}
else
{
buckets[index] = Tuple.Create(Math.Min(buckets[index].Item1, num), Math.Max(buckets[index].Item2, num));
}
}

var result = 0;
Tuple<int, int> lastBucket = null;
for (var i = 0; i < buckets.Length; ++i)
{
if (buckets[i] != null)
{
if (lastBucket != null)
{
result = Math.Max(result, buckets[i].Item1 - lastBucket.Item2);
}
lastBucket = buckets[i];
}
}
return result;
}
}