# C++ 9ms solution

• divide the whole interval into chunks, each with length (max - min - 1)/(n-1) +1;
The maximum gap will not appears in the same chunk. We first put all the numbers into its responding chunks and go through chunk array to find the maximum gap:

``````typedef long long LL;
typedef pair<LL,LL> pLL;
typedef pair<int,int> ii;

class Solution {
public:
int maximumGap(vector<int>& nums) {
int n = nums.size();
if(n<2) return 0;
int m = nums[0], M = nums[0];
for(auto k:nums){
m = min(m,k);
M = max(M,k);
}
if(M==m) return 0;
int L = (M-m-1)/(n-1)+1;
vector<ii> chuck(n,ii(-1,-1));
for(auto k:nums){
int j = (k-m)/L;
if(chuck[j].first == -1){
chuck[j].first = chuck[j].second = k;
}
else{
chuck[j].first = min(chuck[j].first,k);
chuck[j].second = max(chuck[j].second,k);
}
}
int ans = L, tmp = chuck[0].second;
for(int i=1;i<n;++i){
if(chuck[i].first!=-1){
ans = max(chuck[i].first - tmp, ans);
tmp = chuck[i].second;
}
}
return ans;
}
};
``````

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