164. Maximum Gap

Problem:

---

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.

Analysis:

Sort all numbers into buckets. Compare the min value of the current bucket with max value of the previous bucket, we get the possible maximum gap.

The size of bucket is calc from (max - min) / length + 1. The numberOfBuckets is calc from (max - min) / bucketSize + 1.  Then we can easily know which bucket a number belongs to by (number - min) / bucketSize.

 Not all buckets are filled with numbers, we need to skip those empty buckets when comparing for the maximum gap.

Solution:

class Solution {
        public int maximumGap(int[] nums) {
            if (nums.length < 2) return 0;
            int max = nums[0], min = nums[0];
            int len = nums.length;
            for (int n: nums) {
                max = Math.max(n, max);
                min = Math.min(n, min);
            }
            int bucketSize = (max - min) / len + 1;
            int numberOfBuckets = (max - min) / bucketSize +  1;
            int[] minBucket = new int[numberOfBuckets];
            int[] maxBucket = new int[numberOfBuckets];

            Arrays.fill(minBucket, Integer.MAX_VALUE);
            Arrays.fill(maxBucket, Integer.MIN_VALUE);
            Set<Integer> set = new HashSet<>();
            for (int n: nums) {
                int idx = (n - min) / bucketSize;
                set.add(idx);
                minBucket[idx] = Math.min(n, minBucket[idx]);
                maxBucket[idx] = Math.max(n, maxBucket[idx]);
            }
            int prev = max;
            int res = 0;
            for (int i = 0; i < numberOfBuckets; i++) {
                if (!set.contains(i)) continue;
                res = Math.max(res, minBucket[i] - prev);
                prev = maxBucket[i];
            }
            return res;
        }
    }