# Is this bucket sort out of space???

• ``````public static int maximumGap(int[] num) {
if (num.length < 2) return 0;
int maxNum = num[0];
int minNum = num[0];
for (int i : num) {
maxNum=Math.max(maxNum,i);
minNum=Math.min(minNum,i);
}
int len = maxNum - minNum+ 1;
int[] buckets=new int[len];
Arrays.fill(buckets, -1);
for (int x : num) {
int i = x - minNum;
buckets[i]=x;
}
int gap = 0;
int prev = 0;
for (int i = 1; i < buckets.length; i++) {
if (buckets[i]<0) continue;
gap = Math.max(gap, buckets[i] - buckets[prev]);
prev = i;
}
return gap;
}``````

• You can take a look at Use Average Gap to achieve O(n) run time (Java Solution)

Below is a solution using radix sort in java: (However, please suggest a better result.

``````public class MaximumGap {

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

ListNode head = new ListNode(0);
ListNode current = head;
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){
ListNode dummyHead = new ListNode(0);
ListNode current = dummyHead;
for(int i = 0; i < buckets.length; i++){
ListNode currentB = buckets[i];
while(currentB != null){
current.next = currentB;
current = current.next;
currentB = currentB.next;
}
}