## 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; } };