164. Maximum Gap

First of all, this problem can be solved by sorting the array and then check the difference of each adjacent number pairs.

1:  class Solution {  
2:  public:  
3:    int maximumGap(vector<int> &nums) {  
4:      if (nums.size() <= 1) return 0;  
5:      sort(nums.begin(), nums.end());  
6:      int res = nums[1]-nums[0];  
7:      for (int i = 2; i < nums.size(); i++) {  
8:        res = max(res, nums[i] - nums[i-1]);  
9:      }  
10:      return res;  
11:    }  
12:  };  

However, the sort() in c++ is implemented by comparison method which has at least O(nlogn) running time. To achieve O(n) running time, the sort must be implemented by distribution way, i.e. radix sort or bucket sort.

The top rated solution uses bucket sort. The idea is get the maximum number and the minimum number in the array first. So the maximum difference will be (maximum - minimum) and we can sort the number by difference, i.e. (nums[i] - minimum). We'll need n buckets as we have n numbers. So the bucket's length will be (maximum-minimum) / n + 1. If the differences of numbers are uniformly distributed, each bucket will have a number and the maximum difference will be the bucket length. If the differences are not uniformly distributed, some buckets must hold at least two numbers and the maximum difference must be larger than bucket length. Since the maximum difference in one bucket is at most len-1, so the maximum difference won't be taken from one bucket. With that said, we only need to record the maximum number and minimum number in one bucket and discard others between. When calculate gaps, we compute bucket_min[i-1] - bucket_max[i] and pick the largest one (why bucket_min - bucket_max? because these two numbers are adjacent in the sorted array).

Note, there is a corner case that if maximum is equal to minimum, we can return 0 immediately.

1:  /*class Solution {  
2:  public:  
3:    int maximumGap(vector<int> &nums) {  
4:      if (nums.size() <= 1) return 0;  
5:      sort(nums.begin(), nums.end());  
6:      int res = nums[1]-nums[0];  
7:      for (int i = 2; i < nums.size(); i++) {  
8:        res = max(res, nums[i] - nums[i-1]);  
9:      }  
10:      return res;  
11:    }  
12:  };*/  
13:  class Solution {  
14:  public:  
15:  int maximumGap(vector<int>& nums) {  
16:      int n = nums.size();  
17:      if (n <= 1) return 0;  
18:      int maxNum = INT_MIN, minNum = INT_MAX;  
19:      for (int num : nums) {  
20:        maxNum = max(maxNum, num);  
21:        minNum = min(minNum, num);  
22:      }  
23:      int len = (maxNum-minNum) / n+1;  
24:      if (maxNum == minNum) return 0;  
25:      vector<int> maxNums(n, INT_MIN);  
26:      vector<int> minNums(n, INT_MAX);  
27:      for (int i = 0; i < n; i++) {  
28:        int index = (nums[i]-minNum) / len;  
29:        maxNums[index] = max(maxNums[index], nums[i]);  
30:        minNums[index] = min(minNums[index], nums[i]);  
31:      }  
32:      int gap = 0, prev = maxNums[0];  
33:      for (int i = 1; i < n; i++) {  
34:        if (minNums[i] == INT_MAX) continue;  
35:        gap = max(gap, minNums[i]-prev);  
36:        prev = maxNums[i];  
37:      }  
38:      return gap;  
39:    }  
40:  };