Maximum Gap
Medium Bucket sort (pigeonhole)
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the largest difference between consecutive elements after sorting, in linear time and space. Return 0 for fewer than two elements.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the biggest gap between neighbours after sorting, in O(n).
Why this works: with n numbers spread over [min, max], the biggest gap is at least (max-min)/(n-1). Buckets that small can't contain the biggest gap, so only compare between buckets.
Example: [3, 6, 9, 1] → min 1, max 9, bucket size 3
buckets: [1,3], [6], [9]gaps: 6-3 = 3, 9-6 = 3 → answer 3
✦Hints open one at a time
↗Approach
Make n − 1 buckets of size ceil((max − min) / (n − 1)). Store each bucket's min and max. Walk the non-empty buckets; the answer is the largest (bucket min − previous bucket max).
</>Solution (Java)
import java.util.*;
class Solution {
public int maximumGap(int[] nums) {
int n = nums.length;
if (n < 2) return 0;
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
for (int x : nums) { min = Math.min(min, x); max = Math.max(max, x); }
if (min == max) return 0;
int size = Math.max(1, (max - min + n - 2) / (n - 1)); // ceil, at least 1
int count = (max - min) / size + 1;
int[] bMin = new int[count], bMax = new int[count];
Arrays.fill(bMin, Integer.MAX_VALUE);
Arrays.fill(bMax, Integer.MIN_VALUE);
for (int x : nums) {
int b = (x - min) / size;
bMin[b] = Math.min(bMin[b], x);
bMax[b] = Math.max(bMax[b], x);
}
int best = 0, prevMax = min;
for (int b = 0; b < count; b++) {
if (bMin[b] == Integer.MAX_VALUE) continue; // empty bucket
best = Math.max(best, bMin[b] - prevMax); // gap between buckets
prevMax = bMax[b];
}
return best;
}
}!Common mistake
A bucket size of 0 when all values are equal — use at least 1.
- Time: O(n).
- Space: O(n).