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.

Credits:

public class Solution {
    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 n : nums) {
            max = Math.max(max, n);
            min = Math.min(min,n);
        }
        int n = nums.length;
        if (max == min) {
            return 0;
        }
        int gap = (int) Math.ceil((max - min) * 1.0 / (n - 1));
        int maxBucket[] = new int[n];
        for (int i = 0; i < n; i++) {
            maxBucket[i] = Integer.MIN_VALUE;
        }
        int minBucket[] = new int[n];
        Arrays.fill(minBucket, Integer.MAX_VALUE);
        for (int num : nums) {
            int id = (num - min) / gap;
            maxBucket[id] = Math.max(num, maxBucket[id]);
            minBucket[id] = Math.min(num, minBucket[id]);
        }
        int res = 0;
        int preMax = min;
        for (int i = 0; i < n; i++) {
            if (minBucket[i] > maxBucket[i]) {
                continue;
            }
            res = Math.max(res, minBucket[i] - preMax);
            preMax = maxBucket[i];
        }
        return res;
    }
}

====================

public class Solution {
    public int maximumGap(int[] nums) {
        if (nums == null || nums.length < 2) {
            return 0;
        }
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int n : nums) {
            min = Math.min(min, n);
            max = Math.max(max, n);
        }
        if (min == max) {
            return 0;
        }
        HashMap<Integer, int[]> bucket = new HashMap<>();
        int bucketSize = (int) Math.ceil((max - min) * 1.0 / nums.length);
        for (int n : nums) {
         //   if (n == min || n == max) continue;
            int bucketID = (n - min) / bucketSize;
            int[] scope = bucket.get(bucketID);
            if (scope == null) {
                scope = new int[2];
                scope[0] = n;
                scope[1] = n;
                bucket.put(bucketID, scope);
            } else {
                scope[0] = Math.min(scope[0], n);
                scope[1] = Math.max(scope[1], n);
            }
        }
        int res = bucketSize;
        int lastMax = min;
        for (int i = 0; i < nums.length; i++) {
            if (bucket.containsKey(i)) {
                int[] scope = bucket.get(i);
                res = Math.max(res, scope[0] - lastMax);
                lastMax = scope[1];
            }
        }
        res = Math.max(res, max - lastMax);
        return res;
    }
}