164 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.

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        int n = nums.size();
        if ( n <= 1 ) return 0;
        int minnum = nums[0], maxnum = nums[0];
        for ( int i = 1; i <= n-1; i++ ) {
            minnum = min(minnum, nums[i]);
            maxnum = max(maxnum, nums[i]);
        }
        if ( minnum == maxnum ) return 0;
        // maximum gap >= ceiling((maxnum - minnum)/(n-1)) (aka d)
        // minnum ~ minnum + d-1, minnum+d ~ minnum + 2d - 1.....
        // int d = (maxnum - minnum)/(n-1);
        // if ( d*(n-1) < maxnum - minnum ) d += 1;
        // int nbucket = (maxnum - minnum)/d + 1;
        int nbucket = n+1;
        int d = (maxnum - minnum)/(nbucket - 1);
        if ( d*(nbucket-1) < maxnum - minnum ) d += 1;
        vector<int> min_v(nbucket, maxnum), max_v(nbucket, minnum), count(nbucket, 0);
        for ( int i = 0; i <= n-1; i++ ) {
            int j = (nums[i] - minnum)/d;
            min_v[j] = min(min_v[j], nums[i]);
            max_v[j] = max(max_v[j], nums[i]);
            count[j]++;
        }
        int result = 0, n1, i = 0;
        while ( i <= nbucket-1) {
            if ( count[i] != 0 ) n1 = max_v[i];
            i++;
            while ( i <= nbucket - 1 and count[i] == 0 ) i++;
            if ( i == nbucket ) return result;
            result = max(result, min_v[i] - n1);
        }
        return result;
    }
};

Solution

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        int n = nums.size();
        if ( n <= 1 ) return 0;
        int n_min = INT_MAX, n_max = INT_MIN;
        for ( int i = 0; i <= n-1; i++ ) {
            n_min = min(n_min, nums[i]);
            n_max = max(n_max, nums[i]);
        }
        if ( n_max == n_min ) return 0;
        // how many bucket? we want to have an empty one!
        // [ n_min + d*i, n_min+d*(i+1) )
        // last interval is: [ n_min + d*n, n_min+d*(n+1))
        // n_max >= n_min + d*n -> d <= (n_max-n_min)/n;
        // n_max < n_min + d*(n+1) -> d > (n_max-n_min)/(n+1);
        float d = float( n_max-n_min )/n;
        vector<pair<int, int>> bucket(n+1, pair<int, int>(INT_MAX, INT_MIN));
        for ( int i = 0; i <= n-1; i++ ) {
            int j = int((nums[i] - n_min)/d);
            bucket[j].first = min(nums[i], bucket[j].first);
            bucket[j].second = max(nums[i], bucket[j].second);
        }
        int maxGap = 0, low = n_min;
        for ( int i = 0; i <= n; i++ ) {
            if ( bucket[i].first != INT_MAX ) {
                maxGap = max(maxGap, bucket[i].first - low);
                low = bucket[i].second;
            }
        }
        return maxGap;
    }
};

Notes
Bucket sorting Put n numbers into (n+1) buckets, so there are at least one bucket being empty. The inter-bucket gap over an empty bucket must be larger than the intra-bucket gap. Therefore we only have to record the maximum and minimum in each bucket, and evaluate the inter-bucket gap over an empty one!