164 Maximum Gap

164. Maximum Gap

1. Question

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.

2. Implementation

(1) Sort

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

        Arrays.sort(nums);
        int res = 0;

        for (int i = 0; i < nums.length - 1; i++) {
            res = Math.max(res, nums[i + 1] - nums[i]);
        }
        return res;
    }
}

(2) Bucket Sort

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

        int n = nums.length;
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;

        for (int num : nums) {
            min = Math.min(min, num);
            max = Math.max(max, num);
        }

        // 所有元素都一样，不存在gap
        if (min == max) {
            return 0;
        }

        // 计算bucket的长度
        int bucketLen = (int)Math.ceil((double)(max - min) / (n - 1));
        int[] bucketMin = new int[n];
        int[] bucketMax = new int[n];

        Arrays.fill(bucketMin, Integer.MAX_VALUE);
        Arrays.fill(bucketMax, Integer.MIN_VALUE);

        // 将每个数放在对应的bucket，同时记录对应bucket的上限和下限值
        for (int num : nums) {
            int index = (num - min) / bucketLen;
            if (bucketMin[index] == Integer.MAX_VALUE && bucketMax[index] == Integer.MIN_VALUE) {
                bucketMin[index] = num;
                bucketMax[index] = num;
            }
            else {
                bucketMin[index] = Math.min(bucketMin[index], num);
                bucketMax[index] = Math.max(bucketMax[index], num);
            }
        }

        int maxGap = Integer.MIN_VALUE;
        int prev = 0;

        // 计算maxGap
        for (int i = 1; i < n; i++) {
            // 跳过不含有任何数的bucket
            if (bucketMin[i] == Integer.MAX_VALUE && bucketMax[i] == Integer.MIN_VALUE) continue;
            maxGap = Math.max(maxGap, bucketMin[i] - bucketMax[prev]);
            prev = i;
        }
        return maxGap;
    }
}

3. Time & Space Complexity

Sort: 时间复杂度O(nlogn), 空间复杂度O(1)

Bucket Sort: 时间复杂度O(n), 空间复杂度O(n)