Bucket Sort (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.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

Example:

Given [1, 9, 2, 5], the sorted form of it is [1, 2, 5, 9], the maximum gap is between 5 and 9 = 4.

Challenge:

Sort is easy but will cost O(nlogn) time. Try to solve it in linear time and space.

Solution:

We could use bucket sort and put the number into buckets.

Code:

class Solution {
    /**
     * @param nums: an array of integers
     * @return: the maximum difference
     */
    public int maximumGap(int[] nums) {
        if (nums == null || nums.length < 2) {
            return 0;
        }

        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int x : nums) {
            max = Math.max(max, x);
            min = Math.min(min, x);
        }
        if (max == min) {
            return 0;
        }
        int lenOfBucket = (max - min) / nums.length + 1;
        int numOfBuckets = (max - min) / lenOfBucket + 1;
        Bucket[] buckets = new Bucket[numOfBuckets];
        for (int x : nums) {
            int i = (x - min) / lenOfBucket;
            if (buckets[i] == null) {
                buckets[i] = new Bucket(x, x);
            } else {
                buckets[i].max = Math.max(buckets[i].max, x);
                buckets[i].min = Math.min(buckets[i].min, x);
            }

        }

        int gap = 1;
        int prev = 0;
        for (int i = 1; i < numOfBuckets; i++) {
            if (buckets[i] == null) {
                continue;
            }
            gap = Math.max(gap, buckets[i].min - buckets[prev].max);
            prev = i;
        }
        return gap;
    }

    class Bucket {
        int max;
        int min;
        public Bucket(int max, int min) {
            this.max = max;
            this.min = min;
        }
    }
}