# Got run time error on testcase [2,99999999]. Bucket sort.

• I failed to passed testcase [2,99999999] and get the Run Time Error. However the code runs well on my own compiler. Could some one tell me where is the mistake? Thanks!

``````public class Solution {
class Bucket{
int min;
int max;
public Bucket(int m, int n){
max=m;
min=n;
}
}
public int maximumGap(int[] num) {
int len = num.length;
if(len<=1) return 0;
int min=num[0],max=num[0];
//Find max and min in num[]
for(int i:num){
if(i<min) min=i;
if(i>max) max=i;
}
int size = (max-min)/(len-1);
Bucket[] buckets = new Bucket[size];
//Put numbers into buckets
for(int i=0;i<len;i++){
int index = (num[i]-min)/size;
Bucket b = buckets[index];
if(b==null){
b=new Bucket(num[i],num[i]);
}else{
if(num[i]>b.max) b.max=num[i];
if(num[i]<b.min) b.min=num[i];
}
buckets[index]=b;
}
//Find the max gap between buckets
int gap=0,maxgap=0,lastmax=0;
for(int i=0;i<size;i++){
if(buckets[i]!=null){
gap=buckets[i].min-lastmax;
lastmax=buckets[i].max;
if(gap>maxgap) maxgap=gap;
}
}
return maxgap;
}
``````

}

• I use the similar method to solve the problem but I got another Wrong Answer for [15252,16764,27963,7817,26155,20757,3478,22602,20404,6739,16790,10588,16521,6644,20880...].
Do you know how to solve this?

• Its looks like memory requirement violation where you are allocating the memory dynamically. Same thing
happing for me as well with java code.

• U can take a look at details explanation how to use average gap :) here Use Average Gap to achieve O(n) run time (Java Solution)

I've modified your code to get accepted, please take a look at where I put `//changed`

``````public class Solution {
class Bucket{
int min;
int max;
public Bucket(int m, int n){
max=m;
min=n;
}
}
public int maximumGap(int[] num) {
int len = num.length;
if(len<=1) return 0;
int min=num[0],max=num[0];
//Find max and min in num[]
for(int i:num){
if(i<min) min=i;
if(i>max) max=i;
}
int size = (max-min)/(len)+1; //changed
Bucket[] buckets = new Bucket[len]; //changed
//Put numbers into buckets
for(int i=0;i<len;i++){
int index = (num[i]-min)/size;
Bucket b = buckets[index];
if(b==null){
b=new Bucket(num[i],num[i]);
}else{
if(num[i]>b.max) b.max=num[i];
if(num[i]<b.min) b.min=num[i];
}
buckets[index]=b;
}
//Find the max gap between buckets
int gap=0,maxgap=0,lastmax=min; //changed
for(int i=0;i<len;i++){
if(buckets[i]!=null){
gap=buckets[i].min-lastmax;
lastmax=buckets[i].max;
if(gap>maxgap) maxgap=gap;
}
}
return maxgap;
}
}
``````

I think in this problem, you also can use radix sort, which is a special case of bucket sort.

You can reference the following code:

``````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;
}
}