# [recommend for beginners] 2 different clean C++ implementations with detailed explaination

• As far as I am concerned, I think you should grasp the 3 linear-time-sorting-algorithm-implementation introduced at
https://leetcode.com/discuss/80529/recommend-beginners-implementation-detailed-explaination

Then you can quickly understand the following 2 implementation. They are just the small changed version of the original implementation.

``````class Solution {
public:
/* bucket-sort-inspired-ideas-implementation */
int maximumGap(vector<int>& nums) {
const int size_num=nums.size();
if(size_num < 2)    return 0;
int maxV=*max_element(nums.begin(), nums.end());
int minV=*min_element(nums.begin(), nums.end());
if(maxV==minV)  return 0;
double range=(maxV-minV)/double(size_num-1);
cout<<"range:"<<maxV<<"-"<<minV<<"="<<(int)(maxV-minV/double(1))<<endl;
vector<int> max_bucket(size_num, INT_MIN);
vector<int> min_bucket(size_num, INT_MAX);
for(int i=0; i<size_num; i++){
int index=(nums[i]-minV)/range;
max_bucket[index]=max(max_bucket[index], nums[i]);
min_bucket[index]=min(min_bucket[index], nums[i]);
}

int max_gap=(int)range, start=max_bucket[0];
cout<<max_gap<<endl;
for(int i=1; i<size_num; i++){
if(min_bucket[i]==INT_MAX) continue;
max_gap = max(max_gap, min_bucket[i]-start);
start=max_bucket[i];
}
return max_gap;
}

/* radix-based-sorting-implementation */
int maximumGap(vector<int>& nums){
if (nums.size() < 2)	return 0;
int max_val = *max_element(nums.begin(), nums.end());
int exp = 1;
int R = 10;
vector<int> aux(nums.size(), 0);

while (max_val / exp > 0){
vector<int> count(R, 0);
for (int i = 0; i < nums.size(); i++){
count[(nums[i] / exp) % 10]++;
}
for (int i = 1; i < count.size(); i++){
count[i] += count[i - 1];
}
for (int i = nums.size() - 1; i >= 0; i--){
aux[--count[(nums[i] / exp) % 10]] = nums[i];
}

for (int i = 0; i < nums.size(); i++){
nums[i] = aux[i];
}
exp *= 10;
}

int result = 0;
for (int i = 1; i < aux.size(); i++){
result = max(result, aux[i] - aux[i - 1]);
}

return result;
}
};
``````

• Here is the 3-method-implementation-AC-code.

I should notice one possible bug.

``````      int index=len*(nums[i]-min_val)/(double)range;
``````

This code have the potential to be OVER_FLOW !

Why because the big integer multiply big integer can cause overflow if you do not change the type.

So the right way should be like this:

``````     int index=len* ((nums[i]-min_val)/(double)range);
``````

Code:

class Solution {
public:
int maximumGap(vector<int>& nums) {
int n=nums.size();
if(n<=1) return 0;
//countingSort(nums, 1, INT_MAX);
//radixSort(nums);
bucketSort(nums);
int result=0;
for(int i=1; i<n; i++){
result=max(result, nums[i]-nums[i-1]);
}
return result;
}

``````    /** method 1 : only-counting-sort **/
void countingSort(vector<int>& nums){
int len=nums.size();
int range=0;
int start=INT_MAX, end=INT_MIN;
for(int i=0; i<len; i++) { start=min(start, nums[i]);  end=max(end, nums[i]); }
range=end-start+1;
vector<int> count(range,0);
vector<int> result(len,0);
for(int i=0; i<len; i++) count[nums[i]-start]++;
/** loop the [0,range-1] **/
for(int i=1; i<range; i++) count[i]+=count[i-1];
for(int i=len-1; i>=0; i--){
result[count[nums[i]-start]-1]=nums[i];
count[nums[i]-start]--;
}
/** re-assign the result-vector to the original-vector **/
for(int i=0; i<len; i++)  nums[i]=result[i];
return;
}

/** method2 : radix-sort **/
void countingSort(vector<int>& nums, int exp, int base){
#define A(a) ((a/exp)%base)
int n=nums.size();
int start=INT_MAX, end=INT_MIN;
int range=0;
for(int i=0; i<n; i++) { start=min(start, A(nums[i]));  end=max(end, A(nums[i])); }
range=end-start+1;
vector<int> count(range);
vector<int> result(n);
for(int i=0; i<n; i++) { count[A(nums[i])-start]++; }
for(int i=1; i<range; i++) { count[i]+=count[i-1]; }
for(int i=n-1; i>=0; i--){
result[count[A(nums[i])-start]-1]=nums[i];
count[A(nums[i])-start]--;
}
for(int i=0; i<n; i++)  nums[i]=result[i];
}
void radixSort(vector<int> &nums){
int len=nums.size();
int max_val=INT_MIN;
int base=10;
for(int i=0; i<len; i++)  max_val=max(max_val, nums[i]);
for(int exp=1; max_val/exp>0; exp*=base){
countingSort(nums, exp, 10);
}
}

/** method3 : bucket-sort **/
void bucketSort(vector<int>& nums){
int len=nums.size();
int max_val=nums[0], min_val=nums[0];
for(int i=1; i<len; i++) {
max_val=max(max_val, nums[i]);
min_val=min(min_val, nums[i]);
}
int range=max_val-min_val;

if(range==0)  return;
vector<vector<int>> bucket(len+1, vector<int>());

for(int i=0; i<len; i++){
int index=len*((nums[i]-min_val)/(double)range);
bucket[index].push_back(nums[i]);
}
for(int i=0; i<=len; i++) {
if(bucket[i].size()>0)  sort(bucket[i].begin(), bucket[i].end());
}
int index=0;
for(int i=0; i<=len; i++){
for(int j=0; j<bucket[i].size(); j++){
nums[index++]=bucket[i][j];
}
}
}
};``````

• The important intuition is that to infer the gap to be (max-min)/(n-1), then the max_gap must is bigger than that, so we set the intra distance in a bucket is (max-min)/(n-1)

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