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

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

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