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