# Use Average Gap to achieve O(n) run time (Java Solution)

• My idea comes from this: Since the question only allow O(n) run time, I cannot do sorting, (sorting takes at least O(n log n). I can only make use of the O(n) space. Considering the worst case, where the integers are spread by equal distance, like {1,3,5,7,9}. Then the maximum gap is the 2, change any integer in between will leads to larger gap.

So I keep a gaps array which has equal gap distance and non-overlapping range. Like the example {1,3,5,7,9} become {[1,3),[3,5),[5,7),[7,9]}. Let me add some number into it without changing the minimum and maximum bound. {1,3,2,4,5,7,9}. Then, go through the num array, assign lower bound and upper bound for each gap.

The example {1,3,2,4,5,7,9} has gaps

[1,3) with lower bound = 1 and upper bound = 2;

[3,5) with lower bound = 3 and upper bound = 4;

[5,7) with lower bound = 5 and upper bound = 5;

[7,9] with lower bound = 7 and upper bound = 9;

Then go through the gaps array once, you'll be able to find out the maximum gap.

``````public class Solution {
public int maximumGap(int[] num) {
int maxGap = 0;

// edge case
if(num.length < 2){return maxGap;}

// get maximum and minimum
int min = num[0];
int max = num[0];
for(int i = 0;i < num.length;i++){
if(num[i] < min)
min = num[i];
if(num[i] > max)
max = num[i];
}

// divide into identical gaps
Gap[] gaps = new Gap[num.length-1];
boolean[] Engaged = new boolean[num.length-1];
double gap = (double)(max-min)/(double)(num.length-1);
for(int i = 0;i < gaps.length;i++)
Engaged[Math.min((int)Math.floor((double)(num[i]-min)/gap),gaps.length-1)] = true;

// assign maximum and minimum for each gap
for(int i = 0;i < gaps.length;i++)
gaps[i] = new Gap();
for(int i = 0;i < num.length;i++){
int index = (int)Math.floor((double)(num[i]-min)/gap);
index = Math.min(index,gaps.length-1);

// lower bound
if(gaps[index].low == -1)
gaps[index].low = num[i];
else
gaps[index].low = Math.min(gaps[index].low, num[i]);

// upper bound
if(gaps[index].high == -1)
gaps[index].high = num[i];
else
gaps[index].high = Math.max(gaps[index].high, num[i]);
}

// find maximum gap
for(int i = 0;i < gaps.length;i++){
if(Engaged[i]){
// check its inner gap
maxGap = Math.max(gaps[i].high-gaps[i].low, maxGap);

// lower all the way
int j = i;
while(--j >= 0){
if(Engaged[j])
break;
}
if(j >= 0)
maxGap = Math.max(gaps[i].low - gaps[j].high,maxGap);

// upper all the way
j = i;
while(++j < num.length-2){
if(Engaged[j])
break;
}
if(j < gaps.length)
maxGap = Math.max(gaps[j].low - gaps[i].high, maxGap);
}
}

return maxGap;
}

class Gap{
int low;
int high;
Gap(){
low = -1;
high = -1;
}
Gap(int x,int y){
low = x;
high = y;
}
}
}``````

• I think it can be considered as bucket sort.

• Same solution to OP.

``````public class Solution {
public int maximumGap(int[] num) {
if (num.length <= 1) return 0;
if (num.length == 2) return num[0] > num[1] ? (num[0] - num[1]) : (num[1] - num[0]);
// array length must be larger than 2
int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
for (int i = 0; i < num.length; i++) {
if (num[i] > max) max = num[i];
if (num[i] < min) min = num[i];
}
double bucketDelta = ((double)(max - min)) / (num.length - 1);
ArrayList<ArrayList<Integer>> buckets = new ArrayList<ArrayList<Integer>>();
for (int i = 0; i < num.length - 1; i++)

for (int i = 0; i < num.length; i++) {
if (num[i] > min && num[i] < max)
}
int prevMax = min;
ArrayList<Integer> buck;
int idx;
for (idx = 0; idx < num.length - 1; idx++) {
buck = buckets.get(idx);
if (buck.size() == 0) continue;
for (int i : buck)
if (i > prevMax) prevMax = i;
break;
}

int currMin = prevMax, currMax = prevMax;
int maxDiff = 0, diff;
for (++idx; idx < num.length - 1; idx++) {
buck = buckets.get(idx);
if (buck.size() == 0) continue;
currMax = Integer.MIN_VALUE;
currMin = Integer.MAX_VALUE;
for (int j : buck) {
if (j > currMax) currMax = j;
if (j < currMin) currMin = j;
}
diff = currMin - prevMax;
if (diff > maxDiff) maxDiff = diff;
prevMax = currMax;
}
return maxDiff > (max - prevMax) ? maxDiff : max - prevMax;
}}``````

• good explanation on the link.

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