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 < 2) {
            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);
        }

        if (min == max) {
            return 0;
        }

        Bucket buckets[] = new Bucket[n];

        for (int i = 0; i < n; i++) {
            buckets[i] = new Bucket();
        }

        int bucketLen = (int)Math.ceil((double)(max - min) / (n - 1));

        for (int num : nums) {
            int index = (num - min)/bucketLen;

            if (buckets[index].min == Integer.MAX_VALUE) {
                buckets[index].min = num;
                buckets[index].max = num;
            }
            else {
                buckets[index].min = Math.min(buckets[index].min, num);
                buckets[index].max = Math.max(buckets[index].max, num);
            }
        }

        int maxGap = 0, prev = 0;
        for (int i = 1; i < n; i++) {
            if (buckets[i].min != Integer.MAX_VALUE) {
                maxGap = Math.max(maxGap, buckets[i].min - buckets[prev].max);
                prev = i;
            }
        }
        return maxGap;
    }

    class Bucket {
        int min, max;

        public Bucket() {
            min = Integer.MAX_VALUE;
            max = Integer.MIN_VALUE;
        }
    }
}

3. Time & Space Complexity

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

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