# C++ Bucket sort with explanation and clear figure

• /*
Bucket sort

``````Given the MIN and MAX of the array, the gap between MIN and MAX is MAX-MIN, there are n-1 intervals, so the largest
interval length, denoted as maxGap, must be larger than ceiling[(MAX-MIN)/(n-1)]

We construct several buckets with length maxGap, each one is close to another. e.g. [5,1,3,2,4,10]

Bucket
0   1    2    3
|____|____|____|___|
1   3|4  6|7  9|10

we put the numbers into its corresponding bucket

Min 1 2   4         10
Max     3   5       10
|____|____|____|___|
1   3|4  6|7  9|10

to count the maximum different, we can ignore the difference of numbers in the same busket, because they are definitely
smaller than maxGap

***Remark, there are at most n groups, for example, 1, 3, 10, we can get 1-3, 4-6, 7-9 with length 3, and 10
``````

*/

``````class Solution {
public:
int maximumGap(vector<int>& nums) {
int n = nums.size();
if (n < 2) return 0;
if (n == 2) return abs(nums[0] - nums[1]);
vector<int> bucketMin(n, INT_MAX), bucketMax(n, INT_MIN), bucket_cnt(n, 0);
int maxV = INT_MIN, minV = INT_MAX;
for (auto c: nums) {
maxV = max(c, maxV);
minV = min(c, minV);
}
if (maxV - minV == 0) return 0;
int maxGap = (maxV - minV) / (n - 1);
maxGap = maxGap * (n - 1) == (maxV - minV)? maxGap: (maxGap + 1);
for (auto c: nums) {
int bucket_id = (c - minV) / maxGap;
bucket_cnt[bucket_id]++;
bucketMax[bucket_id] = max(bucketMax[bucket_id], c);
bucketMin[bucket_id] = min(bucketMin[bucket_id], c);
}
int maxDistance = INT_MIN;
int lastMax = bucketMin[0];
for (int i = 0; i < n; i++) {
if (bucket_cnt[i] == 0) continue;
maxDistance = max(maxDistance, bucketMin[i] - lastMax);
lastMax = bucketMax[i];
}
return maxDistance;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.