AC solution with N+1 buckets, is it correct?


  • 0
    W

    I came up with the solution using N+1 bucket, where I didn't take the max and min values out of buckets. The idea is if we want at least one bucket is empty for N elements, we must have N+1, and then the size of each bucket is (maxvalue - misvalue + 1)/(N+1).

    The following is the AC code in C++. However, I am not sure the formula to compute bucket size. Maybe it will be wrong for some corn case. Please help me.

    int maximumGap(vector<int> &A) { //bucket sort
        int N = A.size();
        int res = 0;
        if( N <= 1 ) return res;
        
        int minnum = INT_MAX; int maxnum = INT_MIN;
        for( int i = 0; i < N; ++i){
            minnum = minnum > A[i] ? A[i] : minnum;
            maxnum = maxnum < A[i] ? A[i] : maxnum;
        }
        
        int bucketnum = N + 1;
        vector<int> maxbuckets(bucketnum, INT_MIN);
        vector<int> minbuckets(bucketnum, INT_MAX);
        int bucketsize = (maxnum-minnum+1)/(N+1) + 1;
        for( int i = 0; i < N; ++i){
            int id = ( A[i] - minnum)/bucketsize;
            maxbuckets[id] = max(maxbuckets[id],A[i]);
            minbuckets[id] = min(minbuckets[id],A[i]);
        }
        
        int pre = maxbuckets[0];
        for( int id = 1; id < bucketnum; ++id){
            if( minbuckets[id] != INT_MAX ){
                res = max(res, minbuckets[id] - pre);
                pre = maxbuckets[id];
            }
        }
        
        return res;
    }

Log in to reply
 

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