• Time:Time:
• Space:Space:

## C++

``````struct Bucket {
int min;
int max;
};

class Solution {
public:
int maximumGap(vector<int>& nums) {
if (nums.size() < 2)
return 0;

const int mini = *min_element(begin(nums), end(nums));
const int maxi = *max_element(begin(nums), end(nums));
if (mini == maxi)
return 0;

const int gap = ceil((maxi - mini) / (double)(nums.size() - 1));
const int bucketSize = (maxi - mini) / gap + 1;
vector<Bucket> buckets(bucketSize, {INT_MAX, INT_MIN});

for (const int num : nums) {
const int i = (num - mini) / gap;
buckets[i].min = min(buckets[i].min, num);
buckets[i].max = max(buckets[i].max, num);
}

int ans = 0;
int prevMax = mini;

for (const Bucket& bucket : buckets) {
if (bucket.min == INT_MAX)
continue;  // empty bucket
ans = max(ans, bucket.min - prevMax);
prevMax = bucket.max;
}

return ans;
}
};
``````

## JAVA

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

public Bucket(int min, int max) {
this.min = min;
this.max = max;
}
}

class Solution {
public int maximumGap(int[] nums) {
if (nums.length < 2)
return 0;

final int min = Arrays.stream(nums).min().getAsInt();
final int max = Arrays.stream(nums).max().getAsInt();
if (min == max)
return 0;

final int gap = (int) Math.ceil((double) (max - min) / (nums.length - 1));
final int bucketsLength = (max - min) / gap + 1;
Bucket[] buckets = new Bucket[bucketsLength];

for (int i = 0; i < buckets.length; ++i)
buckets[i] = new Bucket(Integer.MAX_VALUE, Integer.MIN_VALUE);

for (final int num : nums) {
final int i = (num - min) / gap;
buckets[i].min = Math.min(buckets[i].min, num);
buckets[i].max = Math.max(buckets[i].max, num);
}

int ans = 0;
int prevMax = min;

for (final Bucket bucket : buckets) {
if (bucket.min == Integer.MAX_VALUE) // empty bucket
continue;
ans = Math.max(ans, bucket.min - prevMax);
prevMax = bucket.max;
}

return ans;
}
}
``````

## Python

``````class Bucket:
def __init__(self, mini: int, maxi: int):
self.mini = mini
self.maxi = maxi

class Solution:
def maximumGap(self, nums: List[int]) -> int:
if len(nums) < 2:
return 0

mini = min(nums)
maxi = max(nums)
if mini == maxi:
return 0

gap = ceil((maxi - mini) / (len(nums) - 1))
bucketSize = (maxi - mini) // gap + 1
buckets = [Bucket(math.inf, -math.inf) for _ in range(bucketSize)]

for num in nums:
i = (num - mini) // gap
buckets[i].mini = min(buckets[i].mini, num)
buckets[i].maxi = max(buckets[i].maxi, num)

ans = 0
prevMax = mini

for bucket in buckets:
if bucket.mini == math.inf:
continue  # empty bucket
ans = max(ans, bucket.mini - prevMax)
prevMax = bucket.maxi

return ans
``````