public int maximumGap(int[] num) {
int n;
if(num == null  (n = num.length) < 2) {
return 0;
}
int min = num[0];
int max = num[0];
for(int i : num) {
if(i > max) {
max = i;
} else if(i < min) {
min = i;
}
}
double dist = (double)(maxmin)/(double)(n1);
int[] mins = new int[n1];
int[] maxs = new int[n1];
Arrays.fill(mins, 1);
Arrays.fill(maxs, 1);
for(int i : num) {
int idx = (i == max ? n2 : (int) ((imin)/dist));
if(mins[idx] == 1  i < mins[idx]) {
mins[idx] = i;
}
if(maxs[idx] == 1  i > maxs[idx]) {
maxs[idx] = i;
}
}
int prevMax = maxs[0];
int maxGap = maxs[0]mins[0];
for(int i = 1; i < n1; i++) {
if(mins[i] == 1) {
continue;
}
int gap = mins[i]  prevMax;
if(gap > maxGap) {
maxGap = gap;
}
prevMax = maxs[i];
}
return maxGap;
}
My accepted java code, time O(n), space O(n)


class Solution { public: int maximumGap(vector<int> &num) { if (num.size()<2) return 0; int max = *max_element(num.begin(), num.end()); int min = *min_element(num.begin(), num.end()); int n = num.size(); vector<int> max_idx(n, 1); vector<int> min_idx(n, 1); for (int i=0; i<n; ++i) { int idx = ((double) (num[i]min) * (n1)) / (maxmin); if (num[i] > max_idx[idx]) max_idx[idx] = num[i]; if (num[i] < min_idx[idx]  min_idx[idx] == 1) min_idx[idx] = num[i]; } int max_gap = 1; int i=0, j=1; while (i<n && j<n) { while (j<n && min_idx[j] == 1) ++j; if (j == n) break; if (min_idx[j]  max_idx[i] > max_gap) max_gap = min_idx[j]  max_idx[i]; i = j; j = j+1; } return max_gap; } };
This is a short C++ version.

I guess it is not quite easy to see what is going on in the code. It takes me some time to figure out, to benefit future viewers, I will just write my understanding here. The idea is to split the range [min, max] evenly int n1 intervals. The interval length would be (max  min)/(n1). According to the pigeon hole principle, the max range cannot be smaller than (max  min)/(n1). Which means if there are two numbers generates the max difference, they must be in different intervals. Then we just need to compute the max difference between successive elements that lies in adjacent intervals. To do that, we just need to record min and max value for each interval.