Maximum Gap

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

• Time: O(n)
• Space: O(1)

public int maximumGap(int[] nums) {
    if (nums.length < 2) return 0;
    int maxGap = 0, max = nums[0], min = nums[0];
    int[] bucketMax = new int[nums.length];
    int[] bucketMin = new int[nums.length];
    Arrays.fill(bucketMax, Integer.MIN_VALUE);
    Arrays.fill(bucketMin, Integer.MAX_VALUE);
    for (int num : nums) {
        max = Math.max(num, max);
        min = Math.min(num, min);
    }
    int gap = (max - min) / nums.length + 1;
    for (int num : nums) {
        if (num == min || num == max) continue;
        int idx = (num - min) / gap;
        bucketMax[idx] = Math.max(bucketMax[idx], num);
        bucketMin[idx] = Math.min(bucketMin[idx], num);
    }
    int pre = min;
    for (int i = 0; i < nums.length - 1; i++) {
        if (bucketMax[i] == Integer.MIN_VALUE && 
            bucketMin[i] == Integer.MAX_VALUE)
            continue;
        if (bucketMin[i] - pre > maxGap)
            maxGap = bucketMin[i] - pre;
        pre = bucketMax[i];
    }
    if (max - pre > maxGap)
        maxGap = max - pre;
    return maxGap;
}