[LintCode/LeetCode] Maximum Gap

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

Return 0 if the array contains less than 2 elements.

Example

Given [1, 9, 2, 5], the sorted form of it is [1, 2, 5, 9], the maximum gap is between 5 and 9 = 4.

Note

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

Challenge

Sort is easy but will cost O(nlogn) time. Try to solve it in linear time and space.

Analysis:

Find the max and min element of the array, and map all elements into n buckets based their relative value to the min value. Element a will be mapped into the index i = (a-min)*(n-1)/(max-min).

Maintain the max and min elements in each bucket. The maximum gap must be one of the gaps of max and min in adjacent buckets.

class Solution {
public:
    int maximumGap(vector<int> nums) {
        // write your code here
        int len = nums.size();
        if(len < 2) return 0;
        int minV = INT_MAX, maxV = INT_MIN;
        for(auto e : nums){
            minV = min(minV, e);
            maxV = max(maxV, e);
        }
        if(maxV == minV) return 0;
        
        float gap = (maxV - minV)/(float)(len-1);
        vector<int> maxBucket(len, INT_MIN),minBucket(len, INT_MAX);

        for(auto e: nums){
            int i = (e-minV)/gap;
            maxBucket[i] = max(maxBucket[i], e);
            minBucket[i] = min(minBucket[i], e);
        }
        
        int previous = minV;
        int res = INT_MIN;
        for(int i=1;i<len;i++){
            if(maxBucket[i] == INT_MIN && 
                minBucket[i] == INT_MAX) continue;
            res = max(res, minBucket[i]-previous);
            previous = maxBucket[i];
        }
        return res;
    }
};