Algorithm

LintCode/Maximum Gap

Problem Summary

Given an unsorted array of N integers, find the maximum difference between the successive elements in its sorted form.

Solution 1: O(NlogN) time

Sort the array with quick sort, merge sort or heap sort. Then iterate through the array.

Solution 2: O(N) time

We know that bucket sort only takes O(N) time to allocate the numbers to buckets. If we make sure that the size of each bucket is small enough, we can save us the trouble of gathering the numbers from buckets.

Actually, once we notice that the lower limit of the answer is L = (max - min)/(N-1), we can set the bucket size to ceil(L) (L rounds up to ceil(l)). Then the maximum difference between numbers in one bucket is at most ceil(L)-1, which is smaller than the answer we want. So we only need to consider the differences of numbers in different buckets. To implement this, we can iterate through each non-empty buckets, and for two adjacent non-empty buckets A and B, we update the answer with the difference between the minimum in B and the maximum in A, i.e. min(B) - max(A).

Code

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
41
42
43
44
45
class Solution {
public:
    /*
     * @param nums: an array of integers
     * @return: the maximun difference
     */
    int maximumGap(vector<int> &nums) {
        int n = nums.size();
        if (n<2)
        	return 0;
        int minv = nums[0], maxv = nums[0];
        for (int i = 1; i < n; ++i)
        {
        	minv = min(minv,nums[i]);
        	maxv = max(maxv,nums[i]);
        }
        if (minv == maxv)
            return 0;
        
        int len = ceil(1.0 * (maxv - minv) / (n-1));
        int m = ceil(1.0 * (maxv - minv) / len) + 1;
        set<int> buckets[m];
        for (int i = 0; i < n; ++i)
        {
        	int cur = (nums[i] - minv)/len;
        	buckets[cur].insert(nums[i]);
        }
        bool is_first = true;
        int last = 0, ans = 0;
        for (int i = 0; i < m; ++i)
        {
        	if (buckets[i].size() == 0)
        		continue;
        	if (is_first)
        		is_first = false;	
        	else
        		ans = max(ans, *buckets[i].begin() - *buckets[last].rbegin());
        	
        	last = i;
        }
        return ans;
    }
};