Maximum Gap

Source

• leetcode: 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.

题解

Understand the problem: We problem is not clearly defined. We can use an example to show. e.g. A[] = {1, 7, 3, 4} In the sorted form, it is 1 3 4 7, and the maximum gap is between 4 and 7, which is 3.

Since the problem asks for O(n) time and space solution, we need to think of using a bucket sorting.

-- Step 1: Calculate the ave. interval. We calculate the min and max of the array A[], and the maximum gap should be in the upper bound of (max - min) / (N - 1). For example, for the example shown above, if the number is uniformly distributed, the gap is (7 - 1) / 3 = 2, i.e, the array should be 1 3 5 7. Since now the number may not be uniformly distributed, the maximum gap might be greater than 2.

-- Step 2: Determine the number of buckets, which should be (max - min) / interval + 1. The number of buckets should be equal to the range of numbers / range per bucket.

-- Step 3: Determine which number is in which bucket, which equals to (A[i] - min) / interval. e.g. (7 - 1) / 2 = 3, in bucket[3].

-- Step 4: We only need to maintain the min and max value for each bucket. The maximum gap must between two adj. buckets instead of within a bucket. That is because the maximum gap inside of a bucket is interval - 1. However, in the step 1 we have already known that the the maximal gap must be greater than interval.

-- Step 5. After we calculated the min and max value in each bucket, we then iterate through the buckets and get the maximal gap between buckets. Be very careful that buckets might be empty.

Java

public class Solution {
    public int maximumGap(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return 0;
        }

        // Step 1: find max and min element
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int num : nums) {
            if (num > max) {
                max = num;
            }

            if (num < min) {
                min = num;
            }
        }

        int len = nums.length;

        // Step 2: calculate the intervals and number of buckets. 
        int interval = (int) Math.ceil((double) (max - min) / (len - 1));
                if (interval == 0) {
            interval = 1;
        }
        int numBuckets = (max - min) / interval + 1;
        Bucket[] buckets = new Bucket[numBuckets];
        for (int i = 0; i < numBuckets; i++) {
            buckets[i] = new Bucket();
        }

        // Step 3: iterate through the nums and assign the number into the buckets. 
        for (int num : nums) {
            int bucketNum = (num - min) / interval;
            if (num > buckets[bucketNum].max) {
                buckets[bucketNum].max = num;
            }

            if (num < buckets[bucketNum].min) {
                buckets[bucketNum].min = num;
            }
        }

        // Step 4: iterate through the buckets and get the maximal gap
        int prev = buckets[0].max;
        int maxGap = 0;
        for (int i = 1; i < numBuckets; i++) {
            if (prev != Integer.MIN_VALUE && buckets[i].min != Integer.MAX_VALUE) {
                maxGap = Math.max(maxGap, buckets[i].min - prev);
                prev = buckets[i].max;
            }
        }

        return maxGap;
    }

    private class Bucket {
        public int min;
        public int max;

        public Bucket() {
            min = Integer.MAX_VALUE;
            max = Integer.MIN_VALUE;
        }
    }
}

Reference

Maximum Gap