The Maximum Gap Problem : Pigeonhole Principle - Algorithms and Problem SolvingAlgorithms and Problem Solving

The Maximum Gap Problem : Pigeonhole Principle - Algorithms and Problem SolvingAlgorithms and Problem Solving

Given a unsorted array with n elements. How can we find the largest gap between consecutive numbers of sorted version in O(n)?

For example, we have a unsorted array, a=[5, 3, 1, 8, 9, 2, 4] of size n=7 then the sorted version is
[1, 2, 3, 4, 5, 8, 9]. The output of the algorithm should be 8-5 = 3.
Similarly, for a=[5, 1, 8, 9, 999999, 99999] then answer should be 999999-99999 = 900000.
One way to do it is to using counting sort or radix sort if the integer range is known and small compared to size of array. But it is not feasible solution in case we don't know the range of the values or the values can be very large.
If we think carefully we will observe that if the array contains n numbers within a contagious sequence of numbers with values between a min and max value (inclusive) then the maximum gap is one. Now, in real problem many of these numbers will be missing. It may happen that some range of values are missing in the sequence and thus creating gaps. If we can identify such missing ranges in a cheap way then we can solve this problem in O(n).

The idea is to bucketize the values between min and max value (exclusive) of the given array into a set of equal sized buckets so that at least one empty bucket is formed. Each of such empty buckets will create a gap of size equals to the difference between max value in the previous non-empty bucket and the minimum value in the next non-empty bucket. The motivation behind this is the Pigeonhole Principle which tells us that if we divide n-1 numbers in n buckets than at least one one bucket is empty

Below is a
 linear‐time 
algorithm 
for
 computing
 the 
maximum
 gap
 allowing
 the
 constant
 time 
computation.


Given
 a 
set 
S 
of 
n
>
2 
real
 numbers
 x1,
x2,
…,
xn.



1. Find
 the
 maximum, 
x­max 
and 
the 
minimum,
 x­min 
in 
S.


2. Divide 
the 
interval 
[x­min,
x­max]
 into
 (n−1) 
"buckets" 
of 
equal 
size
 δ
=
(x­max
–
x­min)/(n‐1).

3. For
 each 
of 
the
 remaining 
n‐2 
numbers 
determine 
in 
which 
bucket
 it 
falls 
using 
the
 floor 
function.
 The number 
xi 
belongs 
to
 the 
kth bucket 
Bk 
if,
 and 
only
 if, 
(xi
‐
x­min)/δ
=
k‐1.

4. For 
each 
bucket 
Bk 
compute 
xk­min 
and xk­max 
among 
the 
numbers
 that
 fall
 in 
Bk. 
If 
the 
bucket 
is 
empty return 
nothing. 
If
the
bucket
 contains 
only 
one
 number 
return 
that 
number 
as
 both
 xk­min 
and xk­max.
5. Construct 
a
 list 
L 
of 
all 
the 
ordered 
minima
 and 
maxima:
 L:
(x1­min,
x1­max),
(x2­min,
x2­max),
…
,
(x(n‐1)­min,
x(n‐1)­max),

        • Note:
Since
 there 
are 
n‐1 
buckets
 and
 only
 n‐2 
numbers,
 by 
the
 Pigeonhole 
Principle, 
at
least 
one bucket
 must 
be 
empty. 
Therefore
 the
 maximum
 distance 
between
 a
 pair
 of
consecutive
 points 
must
 be 
at
 least the 
length 
of 
the 
bucket. 
Therefore
 the
 solution 
is
 not 
found
 among 
a 
pair 
of
 points 
that
 are 
contained
 in the
 same
 bucket.

6. In
 L
 find
 the
 maximum
 distance
 between
 a 
pair 
of
 consecutive
 minimum
 and
 maximum
(xi­max,
xj­min), 
where
j >
i.

7. 
Exit 
with
 this 
number 
as 
the
 maximum 
gap.


For example, with a=[5, 3, 1, 8, 9, 2, 4],

a=[5, 3, 1, 8, 9, 2, 4], n=7
1. Min = 1, Max = 9
2. Create 7-1 = 6 buckets with equal size (or width), δ = (9-1)/(7-1) = 8/6 = 1.33
3. Populate bucket with rest of the 5 elements and compute max and min in each bucket: 
          
          b1    b1    b2    b4    b5    b6
         ____________________________________
        |_2___|__3__|__4__|__5__|______|__8__|
        ^     ^     ^     ^     ^      ^     ^
        1    2.33   3.66  5    6.33   7.66   9

4. Identify all the empty buckets i.e. gaps and compute gap value = max of previous nonempty bucket - min of next non-empty bucket. For example, in this case b5 is an empty bucket, previous non empty bucket is b4 and next non-empty bucket is b6. So, gap value at b5 = max(b5) - min(b6) = 8-5 = 3.
5. Update a global max and iterate over all empty buckets to perform step 3. As there is only one bucket the answer is 3. 

I have implemented the above algorithm using two simple auxiliary arrays to keep track of maximum and minimum in the n-1 buckets with n-2 values (excluding min and max value). The algorithm runs in O(n) time and O(n) space.

public static int maxGap(int[] a){
 int n = a.length;
 if(n < 2){
  return 0;
 }
 
 int max = Integer.MIN_VALUE;
 int min = Integer.MAX_VALUE;
 
 for(int i = 0; i < n; i++){
  max = Math.max(max, a[i]);
  min = Math.min(min, a[i]);
 }
 
 //n-1 buckets -  we only care about max and min in each buckets
 int[] bucketMaxima = new int[n-1];
 Arrays.fill(bucketMaxima, Integer.MIN_VALUE);
 int[] bucketMinima = new int[n-1];
 Arrays.fill(bucketMinima, Integer.MAX_VALUE);
 //bucket width
 float delta = (float)(max-min)/((float)n-1);
 
 //populate the bucket maxima and minima
 for(int i = 0; i < n; i++){
  if(a[i] == max || a[i] == min){
   continue;
  }
  
  int bucketIndex = (int) Math.floor((a[i]-min)/delta);
  bucketMaxima[bucketIndex] = bucketMaxima[bucketIndex] == Integer.MIN_VALUE ? a[i] : Math.max(bucketMaxima[bucketIndex], a[i]);
  bucketMinima[bucketIndex] = bucketMinima[bucketIndex] == Integer.MAX_VALUE ? a[i] : Math.min(bucketMinima[bucketIndex], a[i]);
 }
 
 //find the maxgap - maxgaps
 int prev =  min;
 int maxGap = 0;
 for(int i = 0; i< n-1; i++){
  //empty bucket according to Pigeonhole principle
  if(bucketMinima[i] == Integer.MAX_VALUE){
   continue;
  }
  
  maxGap = Math.max(maxGap, bucketMinima[i]-prev);
  prev = bucketMaxima[i];
 }
 
 maxGap = Math.max(maxGap, max-prev);
 
 return maxGap;
}

http://allenlipeng47.com/PersonalPage/index/view/199/nkey

One solution is by bitmap. Let's go through all elements, and set the bitmap 1 for each element position. Then, we go throught whole bitmap to find the max gap.

Here is a better solution. Let's think about 1, 2, 2, 4. There are 4 elements, let's put them into 5 buckets. Each buckets maintain a distance=(maxValue – minValue)/5=(4-1)/5=0.6 In this way, the bucket will look like:

Then, let’s put each element into each bucket. It will look like:

 Because we choose 5 buckets, then there is at least 1 empty bucket. And we can gurantee the first bucket and last bucket always has element. 

Thus, we know max gap exists between element in left and right bucket of empty bucket. We just find all the empty bucket, then maxValue in its left non-empty bucket, minValue in its right non-empty bucket, gap=minValue-maxValue.

https://github.com/allenlipeng47/algorithm/blob/master/src/main/java/com/pli/project/algorithm/array/MaxGap.java

http://blueocean-penn.blogspot.com/2015/11/max-gap-problem-and-pigoen-hole.html
    public static int maxGap(int[] nums){
        int min = nums[0], max = nums[0];
        for(int k : nums){
            min = Math.min(min, k);
            max = Math.max(max, k);
        }
        
        int size = nums.length;
        int interval = (max-min)/(size-1);
        /*
         * we will create either n-1 or n pigeon holes
         */
        int count = size-1;
        if(interval*count+ min <=max)
            count++;
        
        Integer[] mins = new Integer[count];
        Integer[] maxs = new Integer[count];
        mins[0] = min; maxs[count-1] = max;
        
        for(int k : nums){
            int index = (k-min)/interval;
            mins[index] = mins[index] == null ? k : (Math.min(k, mins[index]));
            maxs[index] = maxs[index] == null ? k : (Math.max(k, maxs[index]));
        }
        
        int maxGap = maxs[0] - mins[0];
        int pre = maxs[0];
        for(int i = 1; i<count; i++){
            if(mins[i]==null)
                continue;
            maxGap = Math.max(mins[i] - pre, maxGap);
            maxGap = Math.max(maxs[i]-mins[i], maxGap);
            pre = maxs[i];
        }
        
        return maxGap;
    }
http://cgm.cs.mcgill.ca/~godfried/teaching/dm-reading-assignments/Maximum-Gap-Problem.pdf
Read full article from The Maximum Gap Problem : Pigeonhole Principle - Algorithms and Problem SolvingAlgorithms and Problem Solving