# Concise AC java: standard buckets

• I believe it's the simplest approach to distributed also min/max. It simplifies also last loop. Regards.

``````public class Solution {
private class Pair {
int min, max;
public Pair(int min, int max) {
this.min = min; this.max = max;
}
}
public int maximumGap(int[] num) {
if (num == null || num.length < 2) {
return 0;
}
int min=num[0], max=num[0], N=num.length;
for (int n: num) {
min = Math.min(min, n);
max = Math.max(max, n);
}
if (max == min) return 0;
int dist=(((max-min)-1)/(N-1))+1;
Pair[] buckets = new Pair[N];
for(int n: num) {
int bucket = (n-min)/dist;
Pair p = buckets[bucket];
if (p == null) {
buckets[bucket] = new Pair(n, n);
} else {
p.min = Math.min(p.min, n);
p.max = Math.max(p.max, n);
}
}
max = dist;
int prevBucketMax=buckets[0].max;
for (int i=1; i<buckets.length; i++) {
if (buckets[i] == null) continue;
max = Math.max(max, buckets[i].min-prevBucketMax);
prevBucketMax = buckets[i].max;
}
return max;
}
}``````

• Another way to implement it (also in java), but the idea of using bucket sort is the same. Since this problem assumes all integers are non-negative, the below code pass. If it includes negative numbers, there is a way to solve it. Anyone can see?

``````public class MaximumGap {

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

for(int i = 0 ; i<num.length; i++){
current.next = new ListNode(num[i]);
current = current.next;
}

int NoBuckets = 10;
ListNode [] buckets;;
ListNode [] bucketTails;

boolean allZero = false;

long n = 1;
while(true){
allZero = true;
bucketTails = new ListNode[NoBuckets];
buckets = new ListNode[NoBuckets];

int i; int j;
while(current!=null){
i = (int) (current.val / n) % 10;
if(current.val >= n) allZero = false;

if(buckets[i] == null) {
buckets[i] = new ListNode(current.val);
bucketTails[i] = buckets[i];
}else{
bucketTails[i].next = new ListNode(current.val);
bucketTails[i] = bucketTails[i].next;
}
current = current.next;
}
if(allZero) break;
n = n*10;
}
int max = current.next.val - current.val; current = current.next;
while(current.next != null){
if(max < current.next.val - current.val) max = current.next.val - current.val;
current = current.next;
}
return max;
}

public ListNode merge(ListNode[] buckets){
for(int i = 0; i < buckets.length; i++){
ListNode currentB = buckets[i];
while(currentB != null){
current.next = currentB;
current = current.next;
currentB = currentB.next;
}
}
}

class ListNode {
int val;
ListNode next;
ListNode(int x){ val = x; }
}

}``````

• How about input with all equal elements? Such as

int[] num = {5,5,5,5};

This implementation returns 1, whereas max gap is 0.

• true! thanks! :)

• I think this is not linear space because you created N new objects of Pair.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.