1 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.

public class Solution {
    public int maximumGap(int[] nums) {

        if(nums.length < 2) return 0;

        int n   = nums.length;
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for(int num: nums){
            max = Math.max(max, num);
            min = Math.min(min, num);
        }
        if(min == max) return 0;

        int gap = (max - min) / n;

        int[] bucket_min = new int[n];
        Arrays.fill(bucket_min, Integer.MAX_VALUE);

        int[] bucket_max = new int[n];
        Arrays.fill(bucket_max, Integer.MIN_VALUE);

        for(int num: nums){

            int i = (num - min)/(gap + 1);
            bucket_min[i] = Math.min(bucket_min[i], num);
            bucket_max[i] = Math.max(bucket_max[i], num);
        }

        Integer pre = null;
        int maxGap = Integer.MIN_VALUE;
        for(int i = 0; i < n; i ++){

            if(bucket_min[i] == Integer.MAX_VALUE) continue;//bucket_max must integer.min_value;

            if(pre != null)
                maxGap = Math.max(maxGap, bucket_min[i] - pre);
            pre = bucket_max[i];

        }

        return maxGap;
    }
}