# [leetcdoe] Maximum Gap

### Maximum Gap

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

Credits:
Special thanks to @porker2008 for adding this problem and creating all test cases.

The question requires linear time and space complexity, so sort algorithm is not suitable. The bottleneck is nlogn.

For N numbers ranges from A to B, the max gap is celling of (B – A) / (N – 1). Therefore, we construct N – 1 buckets whose length is (B – A) / (N – 1). For each number, it falls in to the [(nums[i] – A) / len]th bucket. For each bucket, we just need to store the maximum and minimum number.

Finally, we scan all the buckets to find the maximum gap. It may exists in a same bucket or cross over many buckets.

```//non-negative integer
class Solution {
public:
int maximumGap(vector<int>& nums) {
//extreme case
if(nums.size() < 2) return 0;

int maxNum = nums[0];
int minNum = nums[0];
for(int i = 0; i < nums.size(); i++){
//find max and min
maxNum = maxNum < nums[i]? nums[i]: maxNum;
minNum = minNum < nums[i]? minNum: nums[i];
}
//length of each bucket
int len = (maxNum - minNum) / (nums.size() - 1);

//plus one to make sure each element would fall into a bucket, not over the last bucket
len = len + 1;

//in each bucket, we just need to store the maximum and minimum number
//nums.size() - 1, num of buckets
int min[nums.size() - 1];
int max[nums.size() - 1];

//since elements are non-negative integers, so it's OK to use -1 as a mark
memset(min, -1, sizeof(min));
memset(max, -1, sizeof(max));

for(int i = 0; i < nums.size(); i++){
//bucket index
int idx = (nums[i] - minNum) / len;
if(min[idx] == -1 && max[idx] == -1){
//first element in this bucket
min[idx] = max[idx] = nums[i];
}
else{
min[idx] = nums[i] < min[idx]? nums[i]: min[idx];
max[idx] = nums[i] < max[idx]? max[idx]: nums[i];
}
}

//find the max gap
int maxGap = 0;
int i = 0;
int lastElement = -1;
while(i < nums.size() - 1){
//no elements in this bucket
if(min[i] == -1){
i++;
}
else{
//update internal bucket gap
maxGap = maxGap > (max[i] - min[i])? maxGap: max[i] - min[i];
if(lastElement != -1){
//external bucket gap
maxGap = maxGap > min[i] - lastElement? maxGap: min[i] - lastElement;
//lastElement = max[i]; // BUG
}
lastElement = max[i];//BUG HERE: lastElement
i++;
}
}
return maxGap;
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.