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


  • 0
    E

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

    }


  • 0
    Z

    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?


  • 0
    B

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


  • 1
    D

    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;
            
            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];
                
                current = head.next;
                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;
                }
                head.next = merge(buckets);
                if(allZero) break;
                n = n*10;
            }
            current = head.next;
            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;
                }
            }
            return dummyHead.next;
        }
        
        class ListNode {
            int val;
            ListNode next;
            ListNode(int x){ val = x; }
        }
    
    }
    

Log in to reply
 

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