[LeetCode] 164. Maximum Gap

Posted on | In

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:

1
2
3
4
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:

1
2
3
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.

Explanation

  1. We will use bucket sort approach to solve this problem. Suppose there are N elements and they range from A to B.

  2. Then the maximum gap will be no smaller than ceiling[(B - A) / (N - 1)].

  3. Let the size of a bucket to be len = ceiling[(B - A) / (N - 1)], then we will have at most num = (B - A) / len + 1 of bucket.

  4. For any number K in the array, we can easily find out which bucket it belongs by calculating loc = (K - A) / len and therefore maintain the maximum and minimum elements in each bucket.

  5. Since the maximum difference between elements in the same buckets will be at most len - 1, so the final answer will not be taken from two elements in the same buckets.

  6. For each non-empty buckets p, find the next non-empty buckets q, then q.min - p.max could be the potential answer to the question. Return the maximum of all those values.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    public int maximumGap(int[] nums) {
        if (nums == null || nums.length < 2) return 0;
        if (nums.length == 2) {
            return Math.abs(nums[0]-nums[1]);
        }

        int len = nums.length;
        int min = nums[0], max = nums[0];
        for (int i = 0; i < len; i++) {
            max = Math.max(max, nums[i]);
            min = Math.min(min, nums[i]);
        }

        int gap = (int)Math.ceil((double)(max-min) / (len-1));
        if (gap == 0) return 0;
        int numBucket = (int)Math.floor((double)(max-min) / gap) +1;

        int[] bucketMin = new int[numBucket];
        int[] bucketMax = new int[numBucket];
        Arrays.fill(bucketMin, Integer.MAX_VALUE);
        Arrays.fill(bucketMax, Integer.MIN_VALUE);
        for (int num : nums) {
            if (num == Integer.MIN_VALUE || num == Integer.MAX_VALUE) continue;
            int ind = (int)Math.floor((double)(num - min) / gap);
            bucketMin[ind] = Math.min(bucketMin[ind], num);
            bucketMax[ind] = Math.max(bucketMax[ind], num);
        }

        int res = 0, preMax = bucketMax[0];
        for (int i = 1; i < numBucket; i++) {
            if (bucketMin[i] != Integer.MAX_VALUE) {
                res = Math.max(res, bucketMin[i] - preMax);
                preMax = bucketMax[i];
            }
        }

        return res;
    }
}