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

 

[Thoughts]

Suppose there are N elements and they range from A to B.

Then the maximum gap will be no smaller than ceiling[(B - A) / (N - 1)]

Let the length of a bucket to be len = ceiling[(B - A) / (N - 1)], then we will have at most num = (B - A) / len + 1 of bucket

for any number K in the array, we can easily find out which bucket it belongs by calculating loc = (K - A) / len and therefore maintain the maximum and minimum elements in each bucket.

Since the maximum difference between elements in the same buckets will be at most len - 1, so the final answer will not be taken from two elements in the same buckets.

For each non-empty buckets p, find the next non-empty buckets q, then q.min - p.max could be the potential answer to the question. Return the maximum of all those values.

 

public int maximumGap(int[] num) {
    if (num == null || num.length < 2) return 0;
    // get the max and min value of the array
    int min = num[0];
    int max = num[0];
    for (int val:num) {
        min = Math.min(min, val);
        max = Math.max(max, val);
    }
    // the minimum possibale gap, ceiling of the integer division
    int gap = (int)Math.ceil((double)(max - min)/(num.length - 1));
    int[] bucketsMIN = new int[num.length - 1]; // store the min value in that bucket
    int[] bucketsMAX = new int[num.length - 1]; // store the max value in that bucket
    Arrays.fill(bucketsMIN, Integer.MAX_VALUE);
    Arrays.fill(bucketsMAX, Integer.MIN_VALUE);
    // put numbers into buckets
    for (int val:num) {
        if (val == min || val == max) continue;
        int idx = (val - min) / gap; // index of the right position in the buckets
        bucketsMIN[idx] = Math.min(val, bucketsMIN[idx]);
        bucketsMAX[idx] = Math.max(val, bucketsMAX[idx]);
    }
    // scan the buckets for the max gap
    int maxGap = Integer.MIN_VALUE;
    int previous = min;
    for (int i = 0; i < num.length - 1; i++) {
        if (bucketsMIN[i] == Integer.MAX_VALUE && bucketsMAX[i] == Integer.MIN_VALUE)
            // empty bucket
            continue;
        // min value minus the previous value is the current gap
        maxGap = Math.max(maxGap, bucketsMIN[i] - previous);
        // update previous bucket value
        previous = bucketsMAX[i];
    }
    maxGap = Math.max(maxGap, max - previous); // updata the final max value gap
    return maxGap;
}

 

以上Java代码写的不太好，代码重构成如下：

public int maximumGap(int[] num) {
    if (num == null || num.length < 2) return 0;
    // get the max and min value of the array
    int min = num[0], max = num[0];
    for (int val:num) {
        min = Math.min(min, val);
        max = Math.max(max, val);
    }
    
    // the minimum possibale gap, ceiling of the integer division
    int gap = (int)Math.ceil((double)(max - min)/(num.length - 1));
    int bucketLen = (max - min)/gap + 1; // != num.length - 1
    int[] bucketsMIN = new int[bucketLen]; // store the min value in that bucket
    int[] bucketsMAX = new int[bucketLen]; // store the max value in that bucket
    Arrays.fill(bucketsMIN, Integer.MAX_VALUE);
    Arrays.fill(bucketsMAX, Integer.MIN_VALUE);
    
    // put numbers into buckets
    for (int val:num) {
        int idx = (val - min) / gap; // index of the right position in the buckets
        bucketsMIN[idx] = Math.min(val, bucketsMIN[idx]);
        bucketsMAX[idx] = Math.max(val, bucketsMAX[idx]);
    }
    
    // scan the buckets for the max gap
    int maxGap = 0, prev = min;
    for (int i = 0; i < bucketLen; i++) {
        // empty bucket
        if (bucketsMAX[i] == Integer.MIN_VALUE) continue;
        // min value minus the previous value is the current gap
        maxGap = Math.max(maxGap, bucketsMIN[i] - prev);
        // update previous bucket value
        prev = bucketsMAX[i];
    }
    return maxGap;
}

 

C++版本：

int maximumGap(vector<int> &num) {
    if (num.size() < 2) return 0;
    int minval = INT_MAX, maxval = INT_MIN;
    for (auto v : num) {
        minval = min(v, minval);
        maxval = max(v, maxval);
    }
    double gap = ((double) maxval - minval) / (num.size() - 1);
    vector<pair<int, int> > buckets(num.size() - 1, {-1, -1});
    for (auto v : num) {
        if (v == minval || v == maxval) continue;
        int idx = (v - minval) / gap;
        if (buckets[idx].first == -1) buckets[idx].first = v;
        else buckets[idx].first = min(buckets[idx].first, v);
        buckets[idx].second = max(buckets[idx].second, v);
    }
    int maxdiff = 0, lastval = minval;
    for (auto it : buckets) {
        if (it.first == -1) continue;
        maxdiff = max(maxdiff, it.first - lastval);
        lastval = it.second;
    }
    maxdiff = max(maxdiff, maxval - lastval);
    return maxdiff;
}

Note that the size of each bucket is (max - min) / (n - 1), which is less than or equal to the maximum gap (since we have n - 1 gaps for n numbers, and the total length is max - min). Therefore, the maximum gap can only be the gap between the maximum element in the i-th bucket and the minimum element in the (i+1)-th bucket.

 

An example is, [4, 1, 8, 3, 10, 7] min is 1 and max is 10, the gap is 9/5 = 1.8 so the five buckets are [1, 2.8), is empty (since 1 is minimum and has been ignored) [2.8, 4.6), min is 3 and max is 4 [4.6, 6.4), is empty [6.4, 8.2), min is 7 and max is 8 [8.2, 10), is empty Then we scan these buckets again. If we ignore the empty buckets, it makes sense to compare the following gaps: 3 (min of the second bucket) - 1 (minimum in total) 7 (min of the fourth bucket) - 4 (max of the second bucket) 10 (maximum in total) - 8 (max of the fourth bucket) and we found that the maximum gap is 3.

 

这题本质上是桶排序，首先扫描一遍数组（长度为N）得到最小值和最大值，那么可以得出max gap的下限：
max_gap >= ceil ( (MAX - MIN) / N )
这个下限可以作为bucket的长度，然后可以很容易求出bucket的个数：
num_buckets = (MAX - MIN) / bucket_len + 1
然后重新扫描数组，每个元素K所属bucket的id为(K - MIN) / bucket_len。
扫描的过程中记录每个bucket包含元素的最大值和最小值。

然后对桶进行一次扫描，求出相邻两个非空桶的最大值与最小值之差。这个差的最大值，就是结果。 

int maximumGap(const vector<int> &num) {
    if(num.size() < 2) return 0;
    int min = INT_MAX, max = INT_MIN;
    for(auto i : num) {
        min = std::min(min, i);
        max = std::max(max, i);
    }
    auto ceil_div = [](int x,int y){return (x % y) ? x / y + 1 : x / y;};
    int max_dif = ceil_div(max-min, (int)num.size()-1);
   
    vector<vector<int>> buckets(1 + (max-min)/max_dif, {INT_MAX,INT_MIN});
   
    for(auto i : num) {
        int bucketid = (i - min) / max_dif;
        buckets[bucketid][0] = std::min(buckets[bucketid][0], i);
        buckets[bucketid][1] = std::max(buckets[bucketid][1], i);
    }
   
    int ret = 0, last_nonempty = 0;
    while(buckets[last_nonempty][1] < 0) last_nonempty++;
    for(int i = last_nonempty + 1; i < buckets.size(); ++i) {
        if(buckets[i][1] < 0) continue;
        ret = std::max(ret, buckets[i][0] - buckets[last_nonempty][1]);
        last_nonempty = i;
    }
    return ret;
}

 

Reference:

http://www.fgdsb.com/2015/01/03/maximum-gap/

http://fenghaolw.blogspot.co.uk/2014/12/maximum-gap.html

http://www.programcreek.com/2014/03/leetcode-maximum-gap-java/

http://cgm.cs.mcgill.ca/~godfried/teaching/dm-reading-assignments/Maximum-Gap-Problem.pdf