https://leetcode.com/problems/maximum-gap/
"Straight outta my head" solution
First sort given array, then iterate the sorted elements, compare each element with its next neighbours, maximum gap is the max difference out of these neighbour pairs.
The complexity is the sum of cost of sort function, (at best) nlogn and n-1 times neighbour comparison, hence O(nlogn).
Can we do this better?
Bucket sort is the answer
The rough idea of bucket sort is to place these elements into bucket that accepts certain range (the ranges are non-overlapping). The size of range in which it accepts also known as the bucket size.
Ok, how is bucket sort related to this. Let's us first understand that there are n-1 gaps exists within given array and the sum of these gaps is precisely hi - lo of the array. Bearing this in mind, the maximum gap for the given array will be at least (hi-lo)/(n-1). We can do a simple proof by contradiction by showing that if the maximun gap is less than (hi-lo)/(n-1), given that we have n-1 gaps, the sum of the gap differences will never made up to max-min (therefore validate our statement).
If we have bucket size of (hi-lo)/(n-1), we can disregard the gap of adjacent elements in the same bucket. The max gap will be obtained from the adjacent elements from distinct buckets (by noting the difference between min from current bucket and max from previous bucket).
class Solution {
public int maximumGap(int[] nums) {
// this is like thermometer calibration
int min = nums[0], max = nums[0], n = nums.length;
if (n<2) return 0;
for (int num: nums) {
min = Math.min(min, num);
max = Math.max(max, num);
}
// perform bucket sort
// n is the number of bucket
// (max-min)/(n-1) is the bucket size
int bucketSize = (int) Math.ceil((double) (max - min) / (n - 1));
if (bucketSize == 0) return 0;
int[] maxBucket = new int[n];
int[] minBucket = new int[n];
// !! use max value as marker
Arrays.fill(minBucket, Integer.MAX_VALUE);
for (int x : nums) {
int idx = (x - min) / bucketSize;
minBucket[idx] = Math.min(x, minBucket[idx]);
maxBucket[idx] = Math.max(x, maxBucket[idx]);
}
int maxGap = bucketSize; // Maximum gap is always greater or equal to bucketSize
int previous = maxBucket[0]; // We always have 0th bucket because min always exist
for (int i = 1; i < n; i++) {
if (minBucket[i] == Integer.MAX_VALUE) continue; // Skip empty bucket
maxGap = Math.max(maxGap, minBucket[i] - previous);
previous = maxBucket[i];
}
return maxGap;
}
}