Daily Archives: November 11, 2015

Max Gap between consecutive numbers

Source: http://www.careercup.com/question?id=14764703

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
9 19 13 12 33 41 22
the sorted version is
9 12 13 19 22 33 41
the output of the algorithm should be 33-22 = 11

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 maxValuein its left non-empty bucket, minValue in its right non-empty bucket, gap=minValue-maxValue.

public static int maximumGap(int[] nums) {
    int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
    for (int i : nums) {
        min = Math.min(min, i);
        max = Math.max(max, i);
    }
    int bucketNum = nums.length + 1;
    double interval = (double)(max - min) / bucketNum;
    int[] minBucket = new int[bucketNum];
    int[] maxBucket = new int[bucketNum];
    Arrays.fill(minBucket, Integer.MAX_VALUE);
    Arrays.fill(maxBucket, Integer.MIN_VALUE);
    for (int i = 0; i < nums.length; i++) {
        int bucket = (int)((nums[i] - min) / interval);
        bucket = bucket >= minBucket.length ? bucket - 1 : bucket;
        minBucket[bucket] = Math.min(minBucket[bucket], nums[i]);
        maxBucket[bucket] = Math.max(maxBucket[bucket], nums[i]);
    }
    int ans = 0;
    for (int leftBucket = 0, rightBucket = 1; rightBucket < minBucket.length; rightBucket++) {
        if (minBucket[rightBucket] == Integer.MAX_VALUE) {
            continue;
        }
        ans = Math.max(ans, minBucket[rightBucket] - maxBucket[leftBucket]);
        leftBucket = rightBucket;
    }
    return ans;
}

Check my code on github: link