if (num.size() < 2) return 0;

//find the max & min element

int min=num[0], max=num[0];

for(int i=1; i<num.size(); i++){

min = min > num[i] ? num[i] : min;

max = max < num[i] ? num[i] : max;

}

//Divide the interval [min, max] into n "buckets" of equal size = (max -min)/n

int bucket_size = (max - min)/num.size() + 1;

//For each of the remaining n-2 numbers, determin in which bucket it falls .

//The number num[i] belongs to the kth bucket B[k] if and only if (num[i]-min)/m = k-1

vector< vector<int> > buckets ( (max-min)/bucket_size + 1);

//For each bucket B[k], compute its max & min among the numbers which falls in B[k].

//if the bucket is empty, remain it nothing.

//if the bucket has one number, make this number as both max & min

for(int i=0; i<num.size(); i++){

int idx = (num[i] - min) / bucket_size ;

if (buckets[idx].empty()){

buckets[idx].push_back(num[i]);

buckets[idx].push_back(num[i]);

}else{

buckets[idx][0] = buckets[idx][0] > num[i] ? num[i] : buckets[idx][0];

buckets[idx][1] = buckets[idx][1] < num[i] ? num[i] : buckets[idx][1];

}

}

//calculate the max gap

int maxGap = 0;

int prev = 0;

for (int i = 1; i < buckets.size(); i++) {

if (buckets[i].empty()) continue;

int gap = buckets[i][0] - buckets[prev][1];

maxGap = maxGap > gap ? maxGap : gap;

prev = i;

}

return maxGap;

{

//int a[] = {3, 6, 19, 1};

int a[] = {1,1,1,1,1,5,5,5,5,5};

vector<int> num(a, a+sizeof(a)/sizeof(a[0]));

cout << maximumGap(num) << endl;

return 0;