Massive Algorithms: LeetCode 164

https://leetcode.com/problems/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 1:

Input: [3,6,9,1]
Output: 3
Explanation: The sorted form of the array is [1,3,6,9], either
             (3,6) or (6,9) has the maximum difference 3.

Example 2:

Input: [10]
Output: 0
Explanation: The array contains less than 2 elements, therefore return 0.

Note:

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.
Try to solve it in linear time/space

X. Bucket sort
Pigeon hole principle

http://www.cnblogs.com/grandyang/p/4234970.html
遇到这类问题肯定先想到的是要给数组排序，但是题目要求是要线性的时间和空间，那么只能用桶排序或者基排序。这里我用桶排序Bucket Sort来做，首先找出数组的最大值和最小值，然后要确定每个桶的容量，即为(最大值 - 最小值) / 个数 + 1，在确定桶的个数，即为(最大值 - 最小值) / 桶的容量 + 1，然后需要在每个桶中找出局部最大值和最小值，而最大间距的两个数不会在同一个桶中，而是一个桶的最小值和另一个桶的最大值之间的间距
https://yuanhsh.iteye.com/blog/2187685

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.

https://zhuanlan.zhihu.com/p/55000334

我们首先获取数组的最小值mixnum和最大值maxnum，得到数组的范围.
n个数有n-1个间隔，我们计算平均间隔gap：(maxnum-minnum)/n-1 向上取整.
我们计算需要的桶的个数size = int((maxnum-minnum)/gap)+1个
此题目的关键思想是：在一个桶内的数字之间的差值一定小于gap，如果某两个数之间的差大于平均差gap，一定会被放到两个桶内。最大的差一定大于等于gap（对一组数求平均值，平均值小于等于最大值），于是如果出现了两个数a，b，且a和b的差大于gap，那么a和b一定会被放到两个连续的桶t1，t2内，且a是t1桶的嘴后一个值（最大值），b是t2桶的第一个值（最小值）。于是我们只需要记录每个桶内的最大值和最小值，让后用当前桶内的最小值减去上一个桶内的最大值得到maxgap，取maxgap最大的一个返回即可.
要注意的是，如果在计算平均距离gap时候如果得到了0，说明所有的数相等，这时可以直接返回0.

https://blog.csdn.net/accepthjp/article/details/54098370
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

当所有元素均匀分布的时候，相邻数字的差的最大值最小，因此可以构造桶大小的为[(B - A) / (N - 1)]，

同一个桶内的元素的差一定小于桶的大小，这样就不需要管桶内的大小关系了，只需要关注每个桶的最小值和前一个非空桶的最大值之差就可以了。
那么，线性的排序算法有哪些？计数排序、基数排序、桶排序。
int maximumGap(vector<int>& nums) {
if(nums.size()<2) return 0;
int minn = INT_MAX;
int maxx = INT_MIN;
for(int i = 0; i<nums.size(); i++)
{
minn = min(minn, nums[i]);
maxx = max(maxx, nums[i]);
}
double len = (maxx - minn)*1.0 / (nums.size() - 1);
if(len == 0) return 0;//防止所有元素一样大
int cnt = floor((maxx - minn) / len + 1);
vector<int> minb(cnt, INT_MAX);
vector<int> maxb(cnt, INT_MIN);
for(int i = 0;i<nums.size();i++) //元素分入桶
{
int id = floor((nums[i] - minn) / len);
minb[id] = min(minb[id], nums[i]);
maxb[id] = max(maxb[id], nums[i]);
}
int res = 0, premax = maxb[0];//第一个桶包含最小值，因此一定不为空
for(int i = 1;i<cnt; i++)
{
if(minb[i] != INT_MAX)
{
res = max(res, minb[i] - premax);
premax = maxb[i];
}
}
return res;
}
https://discuss.leetcode.com/topic/5999/bucket-sort-java-solution-with-explanation-o-n-time-and-space

Suppose there are N elements in the array, the min value is min and the max value is max. Then the maximum gap will be no smaller than ceiling[(max - min ) / (N - 1)].

Let gap = ceiling[(max - min ) / (N - 1)]. We divide all numbers in the array into n-1 buckets, where k-th bucket contains all numbers in [min + (k-1)gap, min + k*gap). Since there are n-2 numbers that are not equal min or max and there are n-1 buckets, at least one of the buckets are empty. We only need to store the largest number and the smallest number in each bucket.

After we put all the numbers into the buckets. We can scan the buckets sequentially and get the max gap.

Please correct me if I'm wrong. But why "at least one of the buckets are empty"? Suppose the array is {1,2,3}. The 1st bucket is [1,2) and contains {1}. The 2nd bucket is [2,3] and contains {2,3}. Thus none of the bucket is empty.

Thanks for asking this question.

In this case, 1 and 3 are the min and max. When we put number into the buckets, we'll skip the min and max.

Please see the code blow:

if (i == min || i == max)
continue;

Thanks for your inspiration. I rewrite it in python and make a minor change about the actually needed bucket number
bucketNum = int( math.ceil(float(imax - imin)/gap ) )

instead of num.length - 1 to save space

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 i:num) {
        min = Math.min(min, i);
        max = Math.max(max, i);
    }
    // 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 i:num) {
        if (i == min || i == max)
            continue;
        int idx = (i - min) / gap; // index of the right position in the buckets
        bucketsMIN[idx] = Math.min(i, bucketsMIN[idx]);
        bucketsMAX[idx] = Math.max(i, 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;
}

def maximumGap(self, num):
 if len(num) < 2:
  return 0
 imin = imax = num[0]
 for i in num:
  imin = min(imin,i)
  imax = max(imax,i)
 gap = int( math.ceil( float(imax - imin)/(len(num)-1) ) )
 # actually needed bucket numbers, reduce useless bucket
 bucketNum = int( math.ceil(float(imax - imin)/gap ) )
 bucketMin = [2147483647]* bucketNum
 bucketMax = [0]* bucketNum
 
 for i in num:
  if i == imin or i == imax:
   continue
  idx = (i - imin)/ gap
  bucketMin[idx] = min(bucketMin[idx], i)
  bucketMax[idx] = max(bucketMax[idx], i)
 maxgap = 0
 # consider min
 previous = imin
 for i in range(bucketNum):
  if bucketMin[i] == 2147483647 and bucketMax[i] == 0:
   #empty bucket
   continue
  maxgap = max(maxgap, bucketMin[i] - previous)
  previous = bucketMax[i]
 #consider max
 maxgap = max(maxgap, imax - previous)
 return maxgap

https://yq.aliyun.com/articles/3536
http://www.cnblogs.com/higerzhang/p/4176108.html

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.

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

class Bucket{
    int low;
    int high;
    public Bucket(){
        low = -1;// max_value
        high = -1; //min_value
    }
}
 
public int maximumGap(int[] num) {
    if(num == null || num.length < 2){
        return 0;
    }
 
    int max = num[0];
    int min = num[0];
    for(int i=1; i<num.length; i++){
        max = Math.max(max, num[i]);
        min = Math.min(min, num[i]);
    }
 
    // initialize an array of buckets
    Bucket[] buckets = new Bucket[num.length+1]; //project to (0 - n)
    for(int i=0; i<buckets.length; i++){
        buckets[i] = new Bucket();
    }
 
    double interval = (double) num.length / (max - min);
    //distribute every number to a bucket array
    for(int i=0; i<num.length; i++){
        int index = (int) ((num[i] - min) * interval);
 
        if(buckets[index].low == -1){
            buckets[index].low = num[i];
            buckets[index].high = num[i];
        }else{
            buckets[index].low = Math.min(buckets[index].low, num[i]);
            buckets[index].high = Math.max(buckets[index].high, num[i]);
        }
    }
 
    //scan buckets to find maximum gap
    int result = 0;
    int prev = buckets[0].high;
    for(int i=1; i<buckets.length; i++){
        if(buckets[i].low != -1){
            result = Math.max(result, buckets[i].low-prev);
            prev = buckets[i].high;
        }
 
    }
 
    return result;
}

https://www.cnblogs.com/higerzhang/p/4176108.html

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.

http://2hwp.com/LeetCode/164%20Maximum%20Gap/
http://nb4799.neu.edu/wordpress/?p=1418
This is a problem using the classic ideas of bucketing and pigeon hole principle. The logic is that, we create n+1 buckets between max_num and min_num, where max_num and min_num of the array can be found in O(N) time. Since there are only nnumbers in the array, there must be at least one bucket without any number landing in it. This important factor indicates that the max distance of two consecutive numbers in the sorted form must happen between the maximal number in one previous bucket and the minimal number in one latter bucket and the two buckets have at least one empty bucket between them. Any numbers falling into the same bucket will not have the difference exceeding the bucket range, which is (max_num-min_num)/(n+1).
https://leetcode.com/articles/maximum-gap/#approach-3-buckets-and-the-pigeonhole-principle-accepted

Sorting an entire array can be costly. At worst, it requires comparing each element with every other element. What if we didn't need to compare all pairs of elements? That would be possible if we could somehow divide the elements into representative groups, or rather, buckets. Then we would only need to compare these buckets.

Digression: The Pigeonhole Principle The Pigeonhole Principle states that if $n$ items are put into $m$ containers, with $n > m$ , then at least one container must contain more than one item.

Suppose for each of the

n

elements in our array, there was a bucket. Then each element would occupy one bucket. Now what if we reduced, the number of buckets? Some buckets would have to accommodate more than one element.

Now let's talk about the gaps between the elements. Let's take the best case, where all elements of the array are sorted and have a uniform gap between them. This means every adjacent pair of elements differ by the same constant value. So for

n

elements of the array, there are

n-1

gaps, each of width, say,

t

. It is trivial to deduce that

t = (max - min)/(n-1)

(where

max

and

min

are the minimum and maximum elements of the array). This width is the maximal width/gap between two adjacent elements in the array; precisely the quantity we are looking for!

One can safely argue that this value of

t

, is in fact, the smallest value that

t

can ever accomplish of any array with the same number of elements (i.e.

n

) and the same range (i.e.

(max - min)

). To test this fact, you can start with a uniform width array (as described above) and try to reduce the gap between any two adjacent elements. If you reduce the gap between

arr[i-1]

and

arr[i]

to some value

t - p

, then you will notice that the gap between

arr[i]

and

arr[i+1]

would have increased to

t + p

. Hence the maximum attainable gap would have become

t + p

from

t

. Thus the value of the maximum gap

t

can only increase.

Buckets!

Coming back to our problem, we have already established by application of the Pigeonhole Principle, that if we used buckets instead of individual elements as our base for comparison, the number of comparisons would reduce if we could accommodate more than one element in a single bucket. That does not immediately solve the problem though. What if we had to compare elements within a bucket? We would end up no better.

So the current motivation remains: somehow, if we only had to compare among the buckets, and not the elements within the buckets, we would be good. It would also solve our sorting problem: we would just distribute the elements to the right buckets. Since the buckets can be already ordered, and we only compare among buckets, we wouldn't have to compare all elements to sort them!

But if we only had buckets to compare, we would have to ensure, that the gap between the buckets itself represent the maximal gap in the input array. How do we go about doing that?

We could do that just by setting the buckets to be smaller than

t = (max - min)/(n-1)

(as described above). Since the gaps (between elements) within the same bucket would only be

\leq t

, we could deduce that the maximal gap would indeed occur only between two adjacent buckets.

Hence by setting bucket size

b

to be

1 &lt; b \leq (max - min)/(n-1)

, we can ensure that at least one of the gaps between adjacent buckets would serve as the maximal gap.

Clarifications

A few clarifications are in order:

Would the buckets be of uniform size? Yes. Each of them would be of the same size $b$ .
But, then wouldn't the gap between them be uniform/constant as well? Yes it would be. The gap between them would be $1$ integer unit wide. That means a two adjacent buckets of size $3$ could hold integers with values, say, $3 - 6$ and $7 - 9$ . We avoid overlapping buckets.
Then what are you talking about when you say the gap between two adjacent buckets could be the maximal gap? When we are talking about the size of a bucket, we are talking about its holding capacity. That is the range of values the bucket can represent (or hold). However the actual extent of the bucket are determined by the values of the maximum and minimum element a bucket holds. For example a bucket of size $5$ could have a capacity to hold values between $6 - 10$ . However, if it only holds the elements $7, 8$ and $9$ , then its actual extent is only $(9 - 7) + 1 = 3$ which is not the same as the capacity of the bucket.
Then how do you compare adjacent buckets? We do that by comparing their extents. Thus we compare the minimum element of the next bucket to the maximum element of the current bucket. For example: if we have two buckets of size $5$ each, holding elements $[1, 2, 3]$ and $[9, 10]$ respectively, then the gap between the buckets would essentially refer to the value $9 - 3 = 6$ (which is larger than the size of either bucket).
But then aren't we comparing elements again?! We are, yes! But only compare about twice the elements as the number of buckets (i.e. the minimum and maximum elements of each bucket). If you followed the above, you would realize that this amount is certainly less than the actual number of elements in the array, given a suitable bucket size was chosen.

Algorithm

We choose a bucket size $b$ such that $1 < b \leq (max - min)/(n-1)$ . Let's just choose $b = \lfloor (max - min)/(n-1) \rfloor$ .
Thus all the $n$ elements would be divided among $k = \lceil (max - min)/b \rceil$ buckets.
Hence the $i^{th}$ bucket would hold the range of values: $\bigg [min + (i-1) * b, \space min + i*b \bigg )$ (1-based indexing).
It is trivial to calculate the index of the bucket to which a particular element belongs. That is given by $\lfloor (num - min)/b \rfloor$ (0-based indexing) where $num$ is the element in question.
Once all $n$ elements have been distributed, we compare $k-1$ adjacent bucket pairs to find the maximum gap.

class Bucket {
public:
    bool used = false;
    int minval = numeric_limits<int>::max();        // same as INT_MAX
    int maxval = numeric_limits<int>::min();        // same as INT_MIN
};

int maximumGap(vector<int>& nums)
{
    if (nums.empty() || nums.size() < 2)
        return 0;

    int mini = *min_element(nums.begin(), nums.end()),
        maxi = *max_element(nums.begin(), nums.end());

    int bucketSize = max(1, (maxi - mini) / ((int)nums.size() - 1));        // bucket size or capacity
    int bucketNum = (maxi - mini) / bucketSize + 1;                         // number of buckets
    vector<Bucket> buckets(bucketNum);

    for (auto&& num : nums) {
        int bucketIdx = (num - mini) / bucketSize;                          // locating correct bucket
        buckets[bucketIdx].used = true;
        buckets[bucketIdx].minval = min(num, buckets[bucketIdx].minval);
        buckets[bucketIdx].maxval = max(num, buckets[bucketIdx].maxval);
    }

    int prevBucketMax = mini, maxGap = 0;
    for (auto&& bucket : buckets) {
        if (!bucket.used)
            continue;

        maxGap = max(maxGap, bucket.minval - prevBucketMax);
        prevBucketMax = bucket.maxval;
    }

    return maxGap;
}

https://discuss.leetcode.com/topic/13172/pigeon-hole-principle

Suppose you have n pigeons with labels and you put them into m holes based on their label with each hole of the same size. Why bother putting pigeons into holes? Because you want to disregard the distance between pigeons within each one hole.

Only when at least one hole is empty can we disregard the distance between pigeons within each one hole and compute the maximum gap solely by the distance between pigeons in adjacent holes. We make sure that at least one hole is empty by using m=n-1 (i.e. n-2 pigeons in n-1 holes => at least one hole is empty).

https://en.wikipedia.org/wiki/Pigeonhole_principle

其中一种简单的表述法为：

若有n个笼子和n+1只鸽子，所有的鸽子都被关在鸽笼里，那么至少有一个笼子有至少2只鸽子。

另一种为：

若有n个笼子和kn+1只鸽子，所有的鸽子都被关在鸽笼里，那么至少有一个笼子有至少k+1只鸽子。

一种表达是这样的：如果要把n个物件分配到m个容器中，必有至少一个容器容纳至少⌈n / m⌉个物件。（⌈x⌉大于等于x的最小的整数）

http://zkfairytale.blogspot.ca/2014/12/maximum-gap.html
http://yuanhsh.iteye.com/blog/2187685

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

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 i:num) { min = Math.min(min, i); max = Math.max(max, i); } // 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 i:num) { if (i == min || i == max) continue; int idx = (i - min) / gap; // index of the right position in the buckets bucketsMIN[idx] = Math.min(i, bucketsMIN[idx]); bucketsMAX[idx] = Math.max(i, 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; }

https://discuss.leetcode.com/topic/8354/concise-ac-java-standard-buckets

  private class Pair {
    int min, max;
    public Pair(int min, int max) {
        this.min = min; this.max = max;
    }
  }
  public int maximumGap(int[] num) {
    if (num == null || num.length < 2) {
        return 0;
    }
    int min=num[0], max=num[0], N=num.length;
    for (int n: num) {
        min = Math.min(min, n);
        max = Math.max(max, n);
    }
    if (max == min) return 0;
    int dist=(((max-min)-1)/(N-1))+1;
    Pair[] buckets = new Pair[N];
    for(int n: num) {
        int bucket = (n-min)/dist;
        Pair p = buckets[bucket];
        if (p == null) {
            buckets[bucket] = new Pair(n, n);
        } else {
            p.min = Math.min(p.min, n);
            p.max = Math.max(p.max, n);
        }
    }
    max = dist;
    int prevBucketMax=buckets[0].max;
    for (int i=1; i<buckets.length; i++) {
        if (buckets[i] == null) continue;
        max = Math.max(max, buckets[i].min-prevBucketMax);
        prevBucketMax = buckets[i].max;
    }
    return max;
  }

http://bookshadow.com/weblog/2014/12/14/leetcode-maximum-gap/
http://codesniper.blogspot.com/2015/04/164-maximum-gap-leetcode-java.html

Non-linear time solution. Sort the array and check the gap one by one. O(nlogn).

Linear time solution: Bucket sort.

Assume there are n elements in this array, and the maximum gap must be greater than (max-min)/n-1. Otherwise min+sum(gap[i])<=min+(n-1)*maxGap<max, which is a contradiction.

Therefore, we can divide all elements into (n-1) buckets, and the length of the bucket will be (max-min)/n-1. Since maxGap> (max-min)/n-1, so the two elements that generate the biggest gap must come from two different buckets. For each element in the array, we can easily determine which bucket it located and thus we can maintain a minimumValue and maximumValue for each bucket. By checking bucket[i+1].minValue-bucket[i].maximumValue, we can find the maximum gap.

 public int maximumGap(int[] num) {  
    if(num==null || num.length<2) return 0;  
    int min=Integer.MAX_VALUE;  
    int max=0;  
    for(int i=0;i<num.length;i++){  
      min=Math.min(min,num[i]);  
      max=Math.max(max,num[i]);  
    }  
    int res=(max-min-1)/(num.length-1)+1;  
    int gap=res;  
    int[] minBucket=new int[num.length];  
    for(int i=0;i<num.length;i++) minBucket[i]=max;  
    int[] maxBucket=new int[num.length];  
    for(int i=0;i<num.length;i++){  
      int ind=(num[i]-min)/gap;  
      minBucket[ind]=Math.min(minBucket[ind],num[i]);  
      maxBucket[ind]=Math.max(maxBucket[ind],num[i]);  
    }  
    int pre=0;  
    for(int i=1;i<num.length;i++){  
      if(maxBucket[i]!=0){  
      res=Math.max(res,minBucket[i]-maxBucket[pre]);  
      pre=i;  
      }  
    }  
    return res;  
   }

X.
http://buttercola.blogspot.com/2015/08/leetcode-maximum-gap.html
X. Radix Sort
https://discuss.leetcode.com/topic/22221/radix-sort-solution-in-java-with-explanation

public int maximumGap(int[] nums) {
    if (nums == null || nums.length < 2) {
        return 0;
    }
    
    // m is the maximal number in nums
    int m = nums[0];
    for (int i = 1; i < nums.length; i++) {
        m = Math.max(m, nums[i]);
    }
    
    int exp = 1; // 1, 10, 100, 1000 ...
    int R = 10; // 10 digits

    int[] aux = new int[nums.length];
    
    while (m / exp > 0) { // Go through all digits from LSB to MSB
        int[] count = new int[R];
        
        for (int i = 0; i < nums.length; i++) {
            count[(nums[i] / exp) % 10]++;
        }
        
        for (int i = 1; i < count.length; i++) {
            count[i] += count[i - 1];
        }
        
        for (int i = nums.length - 1; i >= 0; i--) {
            aux[--count[(nums[i] / exp) % 10]] = nums[i];
        }
        
        for (int i = 0; i < nums.length; i++) {
            nums[i] = aux[i];
        }
        exp *= 10;
    }
    
    int max = 0;
    for (int i = 1; i < aux.length; i++) {
        max = Math.max(max, aux[i] - aux[i - 1]);
    }
     
    return max;
}

https://discuss.leetcode.com/topic/5996/i-solved-it-using-radix-sort/16

    private List<Integer> radixSort(int[] arr) {
        List<List<Integer>> radix = new ArrayList<>();
        for (int i = 0; i < 10; i++) radix.add(new LinkedList<Integer>());
        for (int n : arr) radix.get(n % 10).add(n);
        for (int i = 1; i < 10; i++) {
            List<List<Integer>> newRadix = new ArrayList<>();
            for (int j = 0; j < 10; j++) newRadix.add(new LinkedList<Integer>());
            for (List<Integer> qr : radix) {
                for (int n : qr) {
                    int tmp = n;
                    for (int k = i; k > 0; k--) n /= 10;
                    newRadix.get(n % 10).add(tmp);
                }
            }
            radix = newRadix;
        }
        return radix.get(0);
    }

    public int maximumGap(int[] num) {
        if (num.length < 2) return 0;
        int prev = Integer.MIN_VALUE, maxGap = Integer.MIN_VALUE;
        for (int n : radixSort(num)) {
            maxGap = Math.max(n - prev, maxGap);
            prev = n;
        }
        return maxGap;
    }

https://discuss.leetcode.com/topic/51902/java-radix-sort

    public int maximumGap(int[] nums) {
        if(nums == null || nums.length == 0 || nums.length == 1) {
            return 0;
        }
        int res = 0;
        radixsort(nums);
        for(int i = 1 ; i < nums.length ; i++) {
            res = Math.max(res , nums[i] - nums[i-1]);
        }
        return res;
    }
    
    protected void radixsort(int[] nums) {
        int[] temp = new int[nums.length];
        for(int i = 0 ; i < 32 ; i++) {
            int[] c = new int[2];
            for(int num : nums) {
                int digit = num >> i;
                if((digit & 1) == 0) c[0]++;
                else c[1]++;
            }
            c[1] = c[0] + c[1];
            for(int j = nums.length-1 ; j >= 0 ; j--) {
                int digit = (nums[j] >> i) & 1;
                temp[c[digit]-1] = nums[j];
                c[digit]--;
            }
            for(int j = 0 ; j < nums.length ; j++) {
                nums[j] = temp[j];
            }
        }
    }

https://leetcode.com/discuss/53636/radix-sort-solution-in-java-with-explanation

The first step is to find the maximum value in nums array, it will be the threshold to end while loop.
Then use the radix sort algorithm to sort based on each digit from Least Significant Bit (LSB) to Most Significant Bit (MSB), that's exactly what's showing in the link.
(nums[i] / exp) % 10 is used to get the digit, for each digit, basically the digit itself serves as the index to access the count array. Count array stores the index to access aux array which stores the numbers after sorting based on the current digit.
Finally, find the maximum gap from sorted array.

Time and space complexities are both O(n). (Actually time is O(10n) at worst case for Integer.MAX_VALUE 2147483647)

public int maximumGap(int[] nums) { if (nums == null || nums.length < 2) { return 0; } // m is the maximal number in nums int m = nums[0]; for (int i = 1; i < nums.length; i++) { m = Math.max(m, nums[i]); } int exp = 1; // 1, 10, 100, 1000 ... int R = 10; // 10 digits int[] aux = new int[nums.length]; while (m / exp > 0) { // Go through all digits from LSB to MSB int[] count = new int[R]; for (int i = 0; i < nums.length; i++) { count[(nums[i] / exp) % 10]++; } for (int i = 1; i < count.length; i++) { count[i] += count[i - 1]; } for (int i = nums.length - 1; i >= 0; i--) { aux[--count[(nums[i] / exp) % 10]] = nums[i]; } for (int i = 0; i < nums.length; i++) { nums[i] = aux[i]; } exp *= 10; } int max = 0; for (int i = 1; i < aux.length; i++) { max = Math.max(max, aux[i] - aux[i - 1]); } return max; }
http://www.jiuzhang.com/solutions/maximum-gap/

X.
http://www.cnblogs.com/yrbbest/p/4491632.html

给定未排序数组，求两个相邻元素间的差的最大值。想了一会不确定，于是去看了一眼Discuss的标题，果然是用Radix Sort。其实一开始看到题目里面所有数字都可以被表示为32-bit signed integer时，就应该要想到才对。估计做法就是用Radix Sort，排序完毕后再扫描一边数组。正好加深一下对Radix Sort的理解和书写。要好好研究一下Key-indexed Counting，LSD，MSD和Bucket Sort。这道题用Bucket Sort的话就是把每个元素放入一个bucket中，然后计算非空bucket间的最大距离，原理都差不多。一刷用了LSD，代码大都参考Sedgewick大神，二刷的话要试一试MSD以及bucket sort。注意的一点是LSD处理最高8位bit时， 0 ~ 127为正， 128 ~ 255为负，所以要特殊处理一下accumulated count数组。做完这题以后就发现上过算法2真好...

LSD Radix Sort, Time Complexity - O(n), Space Complexity - O(n)

public class Solution {
    public int maximumGap(int[] nums) {
        if(nums == null || nums.length < 2)
            return 0;
        lsdSort(nums);
        int maxDiff = Integer.MIN_VALUE;
        for(int i = 1; i < nums.length; i++)
            maxDiff = Math.max(nums[i] - nums[i - 1], maxDiff);         //may overflow
        return maxDiff;
    }
    
    private void lsdSort(int[] nums) {
        int len = nums.length;
        int[] aux = new int[nums.length];
        int totalBits = 32;
        int bitsPerByte = 8;
        int window = totalBits / bitsPerByte;
        int R = 1 << bitsPerByte;           // R is radix
        int mask = R - 1; // 11111111
        
        for(int d = 0; d < window; d++) {            // for each window compared
            int[] count = new int[R + 1];
            
            for(int i = 0; i < len; i++) {      // count least significant 8 bits of each num in nums
                int c = (nums[i] >> (d * bitsPerByte)) & mask;  // use mask to get least significant 8 bits
                count[c + 1]++;
            }        
            
            for(int i = 0; i < R; i++)          // count accumulated position for each nums
                count[i + 1] += count[i]; 
            
            if(d == window - 1) {        // for most significant 8 bits,  0 ~ 127 is pos, 128 ~ 255 is neg, so 128 ~ 255 goes first
                int shift1 = count[R] - count[R / 2];
                int shift2 = count[R / 2];
                for(int i = 0; i < R / 2; i++)
                    count[i] += shift1;
                for(int i = R / 2; i < R; i++)
                    count[i] -= shift2;
            }
            
            for(int i = 0; i < len; i++) {      // move data
                int c = (nums[i] >> (d * bitsPerByte)) & mask;
                aux[count[c]++] = nums[i];
            }
                
            for(int i = 0; i < len; i++)        // copy back
                nums[i] = aux[i];
        }
        
    }
}

二刷:

依然使用了LSD radix sort，代码大都来自塞神的index counting。

我们把32位的数字分为4个batch，每个batch有8个digit，使用LSD的话我们是从最低一级的batch开始计算。这里我们要使用一个mask = 255，也就是二进制的11111111来找到每个batch。也要做一个auxiliary array - aux[] 用来保存临时结果
对于每个batch，我们都要做一次index counting sort，一共四次，从最低8位开始，到最高8位

每次确定了batch之后我们就可以创建buckets数组。这里buckets数组 count = new int[R + 1] ，这里的 + 1很重要
我们第一次遍历数组，根据最低8位，统计所有数字出现的频率，然后放入相应的bucket里，这里有个小trick很关键，我们虽然将低8位映射到从[0 - 255]这样的256个bucket里，但写入count数组的时候，我们有意把count[0]留下，把数字的count写到 [1 - 256]的bucket中。这样做的好处，要在后面才能看到，就是从经过aggregation后的count数组，将排序后的数字填入到aux[]数组中时。
然后，我们对统计好的数字和频率进行aggregation，利用count数组求一个accumulated count。经历过这一步以后，我们的count[i]代表的意思就是，有多少个数字应该被放在 i 之前的buckets里。
接下来，我们根据aggregation的结果，我们把这些数字填到aux[]里
最后把aux[]中的数字拷贝回nums中，继续计算下一个batch。因为LSD的操作是stable的，所以我们进行完全部4个batch以后就会得到最终结果

这里要注意的一点是，32位数字最高8位digit的这个batch和其他三个不同。在这8位里0 ~ 127为正数，而128 ~ 255为负数。所以在这个batch里，计算完aggregation数组后，我们要做一个很巧妙的shift操作
1. 先求出shift1 = count[R] - count[R / 2], 也就是在输入的nums[]中有多少个数字为负
2. 再求出shift2 = count[R / 2]，输入的nums[]中有多少个正数
3. 对于[0 - 127]的这些数字，他们都应该排在负数前面，所以我们对每一个count[i] 增加 shift1
4. 对于[128 - 255]的这些数字，他们都应该排在正数后面，所以我们对每一个count[i] 减少 shift2
5. 之后再根据新的count[]数组，把数字放入aux[]数组中，再拷贝回原数组nums[]里。

Java:

Time Complexity - O(n), Space Complexity - O(n)

public class Solution {
    public int maximumGap(int[] nums) {    // LSD
        LSDradix(nums);
        int maxGap = 0;
        for (int i = 1; i < nums.length; i++) maxGap = Math.max(maxGap, nums[i] - nums[i - 1]);
        return maxGap;
    }
    
    private void LSDradix(int[] nums) {
        if (nums == null || nums.length == 0) return;
        int batchSize = 8;
        int batchNum = 32 / batchSize;
        int R = 1 << batchSize;      // radix, each bucket we consider only [0 - 255] , 256 numbers
        int mask = R - 1;            // 11111111, each batch 8 digits
        int len = nums.length;
        int[] aux = new int[len];
        
        for (int d = 0; d < batchNum; d++) {
            int[] count = new int[R + 1];
            for (int num : nums) {
                int idx = (num >> (d * batchSize)) & mask;
                count[idx + 1]++;      // index counting
            }
            for (int k = 1; k < count.length; k++) count[k] += count[k - 1];    // aggregation, find out the buckets boundaries
            if (d == batchNum - 1) {            // for first 8 digits 01111111 is max,  11111111 is min, we shift nums
                int shift1 = count[R] - count[R / 2];
                int shift2 = count[R / 2];
                for (int k = 0; k < R / 2; k++) count[k] += shift1;
                for (int k = R / 2; k < R; k++) count[k] -= shift2;
            }
            for (int num : nums) {
                int idx = (num >> (d * batchSize)) & mask;
                aux[count[idx]++] = num;    // we place each num in each buckets, from the start slot of the bucket
            }
            for (int k = 0; k < len; k++) nums[k] = aux[k];
        }
    }
}

http://easyleetcode.blogspot.com/2015/01/leetcode-164-maximum-gap.html

The linear time constraint means we can not sort the array. However, we can use linear space, not constant space!! Therefore, we can trade space for time. We can use the idea similar to bucket sort:

Set up an array of initially empty "buckets".
Scatter: Go over the original array, putting each object in its bucket.
Sort each non-empty bucket.
Gather: Visit the buckets in order and put all elements back into the original array.

However, because we have linear time constraint, we cannot go step 3: sort each non-empty bucket. Therefore, we have to make the size of bucket as 1 element.

Algorithm:

Find the buckets boundary: the max and min values of the array.
Construct (n-1) bucket: the bucket size = (max-min)/(n-1)
Put the rest (n-2) numbers into (n-1) buckets, except max and min value: must has at least 1 empty bucket. Therefore, for max gap, no need to consider gap within buckets.
Iterate (n-1) buckets: find the maximum gap between each bucket and its neighbors.

For example, we have an array of [5, 6, 4,1,2] the max gap is 4-2=2.

Find the buckets boundary: max=6, min=1
Construct (n-1) buckets: size=5/4=1.25, b1=[1, 2.25], b2=(2.25, 3.5], b3=(3.5, 4.75], b4=(4.75,6]
Put the rest (n-2) numbers into (n-1) buckets: {b1:[2], b2:[], b3:[4], b4:[5]}, here b2 is empty
For non-empty buckets: the gap between b1 and b3 is max [4]-[2]

def maximumGap(self, num):
        if len(num) <2:
            return 0

        # Application of Pigeonhole Principle
        max_val = max(num)
        min_val = min(num)

        # Initialize buckets
        n = len(num)
        buckets = [[] for i in range(n-1)]
        bucket_size = (max_val-min_val)/float( (n-1) )

        # Construct buckets for (n-2) numbers
        for number in num:
            if number == max_val or number == min_val:
                continue
            k = int( math.floor( (number - min_val)/bucket_size) )
            buckets[k].append(number)

        L = [] # non-empty buckets
        for b in buckets:
            if b!=[]:
                L.append( b ) 

        # According to Pigeon Principle, at least 1 bucket is empty
        # The maximum gap should be gap between 2 elements from 2 successive bucket
        # Initial max gap should be gap either between min-val and first non-empty bucket (minimum) or between max_val and last non-empty bucket
        if L==[]:
            return max_val - min_val
        max_gap = max(min(L[0])-min_val, max_val-max(L[-1]) )
        for i in range(1, len(L)):
            gap = min(L[i]) - max( L[i-1] )
            max_gap = max(max_gap, gap)
                
        return max_gap

https://leetcode.com/articles/maximum-gap/

int maximumGap(vector<int>& nums)
{
    if (nums.empty() || nums.size() < 2)            // check if array is empty or small sized
        return 0;

    sort(nums.begin(), nums.end());                 // sort the array

    int maxGap = 0;

    for (int i = 0; i < nums.size() - 1; i++)
        maxGap = max(nums[i + 1] - nums[i], maxGap);

    return maxGap;
}

http://dmwlxz.blogspot.com/2016/05/leetcode-164-maximum-gap.html
Read full article from 【leetcode 桶排序】Maximum Gap - wepon的专栏 - 博客频道 - CSDN.NET

LeetCode 164 - Maximum Gap

Algorithm:

Labels

Popular Posts