# C++ solution with O(n) time and space

• ``````class Solution {
public:
int maximumGap(vector<int> &num) {
// 1、find max and min elemnet
if (num.size()<2) return 0;
if (num.size()==2) return abs(num[0]-num[1]);
int min_num = INT_MAX;
int max_num = INT_MIN;
int i;
for (i=0; i<num.size(); i++) {
if (num[i]<min_num)
min_num = num[i];
if (num[i]>max_num)
max_num = num[i];
}
//2、create buckets, every bucket store min and max element if exit;
int gap = (max_num-min_num)/(num.size()-1)+1;
vector<vector<int> > temp(num.size());

for(i=0; i<num.size(); i++) {
int index = (num[i]-min_num)/gap;
if (temp[index].empty())
temp[index].push_back(num[i]);
else if (temp[index].size()==1) {
if (num[i]<temp[index][0]) {
temp[index].push_back(temp[index][0]);
temp[index][0] = num[i];
} else
temp[index].push_back(num[i]);
} else {
if (num[i]<temp[index][0])
temp[index][0] = num[i];
if (num[i]>temp[index][1])
temp[index][1] = num[i];
}
}
//3、find max gap between bucket
int ret=INT_MIN;
vector<int> pre = temp[0];
for (i=1; i<temp.size(); i++) {
if (temp[i].empty())
continue;
if (pre.size()==1) {
if (temp[i][0]-pre[0]>ret)
ret = temp[i][0]-pre[0];
} else {
if (temp[i][0]-pre[1]>ret)
ret = temp[i][0]-pre[1];
}
pre = temp[i];
}

return ret;
}
};``````

• Your code won't save much space, so no need to make it a mess.

Here is mine:

``````class Solution {
public:
int maximumGap(vector<int> &num) {
if (num.size() < 2) return 0;
// find the minimum and the maximum
int imax = num[0];
int imin = num[0];
for (int x : num) {
if (x > imax) imax = x;
if (x < imin) imin = x;
}
// each bucket has at most m numbers
int m = (imax - imin) / num.size() + 1;
// but we just need the minimum and the maximum of each bucket
vector<vector<int>> buckets((imax - imin) / m + 1);
for (int x : num) {
int i = (x - imin) / m;
if (buckets[i].empty()) {
buckets[i].reserve(2);
buckets[i].push_back(x);
buckets[i].push_back(x);
} else {
if (x < buckets[i][0]) buckets[i][0] = x;
if (x > buckets[i][1]) buckets[i][1] = x;
}
}
// calculate the maximal gap
int gap = 0;
int prev = 0;
for (int i = 1; i < buckets.size(); i++) {
if (buckets[i].empty()) continue;
gap = max(gap, buckets[i][0] - buckets[prev][1]);
prev = i;
}
return gap;
}
};``````

• An alternative: The vector of vectors you have makes a memory allocations for every non-empty bucket. Instead you could just make two vectors and use sentinel values (e.g. -1) for the empty buckets.

• Thanks. It is really more efficient. :)

• nice implementation

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