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.

Example 1:

Input:
 [3,6,9,1]

Output:
 3

Explanation:
 The sorted form of the array is [1,3,6,9], either
             (3,6) or (6,9) has the maximum difference 3.

Example 2:

Input:
 [10]

Output:
 0

Explanation:
 The array contains less than 2 elements, therefore return 0.

Note:

• You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.
• Try to solve it in linear time/space.

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

        int min = nums[0], max = nums[0], n = nums.length;
        for (int num : nums){
            min = Math.min(min, num);
            max = Math.max(max, num);
        }
        int gap = (int)Math.ceil( (double)(max - min) / (n - 1) );

        int[] gapMin = new int[n - 1];
        int[] gapMax = new int[n - 1];

        Arrays.fill(gapMin, Integer.MAX_VALUE);
        Arrays.fill(gapMax, Integer.MIN_VALUE);

        for (int num : nums){
            if (num == min || num == max) continue;

            int index = (num - min) / gap;

            //System.out.println("n: " + n + " index: " + index + " gap: " + gap + " max: " + max + " min: " + min);
            gapMin[index] = Math.min(gapMin[index], num);
            gapMax[index] = Math.max(gapMax[index], num);
        }

        int prev = min, ans = 0;
        for (int i = 0; i < n - 1; i++){
            if (gapMin[i] == Integer.MAX_VALUE && gapMax[i] == Integer.MIN_VALUE) continue;

            ans = Math.max(ans, gapMin[i] - prev);
            prev = gapMax[i];
        }
        ans = Math.max(max - prev, ans);

        return ans;
    }
}