Maximum Gap
Description
Given an array of non-negative integers nums, return the largest difference between two neighbours once the array is sorted. If it has fewer than two values, return 0.
Your algorithm must run in linear time and use linear extra space.
Examples
Example 1
Input: nums = [3, 6, 9, 1]
Output: 3
Explanation: Sorted, it's 1 3 6 9: the gaps are 2, 3 and 3, so 3.
Example 2
Input: nums = [10]
Output: 0
Explanation: Fewer than two values: there's no gap, so 0.
Example 3
Input: nums = [1, 1, 1, 1]
Output: 0
Explanation: All the values are equal: every gap is 0.
Example 4
Input: nums = [1, 10000000]
Output: 9999999
Explanation: Two values: the one gap is 10,000,000 − 1 = 9,999,999.
Constraints
- 1 ≤ nums.length ≤ 10⁵
- 0 ≤ nums[i] ≤ 10⁹
Editorial
Brute Force
Intuition
The gaps are between neighbours in sorted order, so sort the values and look at each neighbouring pair: the largest difference is the answer.
Step-by-Step Explanation
Let's trace Example 1, nums = [3, 6, 9, 1]:
- Sort: 1 3 6 9.
- The gaps are 2, 3, 3; the largest is 3.
Sort, Then Scan the Neighbours — The sorted values, each neighbouring pair compared in turn.
Algorithm
- Sort a copy of the values.
- For each neighbouring pair, keep the largest difference.
- Return it (0 when there are fewer than two values).
Code
class Solution {
public:
int maximumGap(vector<int>& nums) {
vector<int> sorted = nums;
sort(sorted.begin(), sorted.end()); // O(n log n)
int best = 0;
for (size_t i = 1; i < sorted.size(); i++)
best = max(best, sorted[i] - sorted[i - 1]); // neighbours in sorted order
return best;
}
};
class Solution:
def maximumGap(self, nums: List[int]) -> int:
s = sorted(nums) # O(n log n)
best = 0
for a, b in zip(s, s[1:]): # neighbours in sorted order
best = max(best, b - a)
return best
class Solution {
public int maximumGap(int[] nums) {
int[] sorted = nums.clone();
java.util.Arrays.sort(sorted); // O(n log n)
int best = 0;
for (int i = 1; i < sorted.length; i++)
best = Math.max(best, sorted[i] - sorted[i - 1]); // neighbours in sorted order
return best;
}
}
var maximumGap = function(nums) {
const sorted = nums.slice().sort((a, b) => a - b); // O(n log n)
let best = 0;
for (let i = 1; i < sorted.length; i++)
best = Math.max(best, sorted[i] - sorted[i - 1]); // neighbours in sorted order
return best;
};
Complexity Analysis
Time Complexity: O(n log n)
The sort; the scan after it is O(n).
Space Complexity: O(n)
The sorted copy.
Why This Approach Is Not Efficient
It passes every test here, but the problem asks for linear time, and sorting by comparing can't get there: some order of n values needs about n log₂ n comparisons (Counting, Bucket and Radix Sort shows why). Radix sort, which never compares, would get the order in linear time, but the answer doesn't need the whole order, only the largest jump.
n values have n − 1 gaps that add up to hi − lo, so the largest is at least their average. Values closer together than that can share a bucket without hiding the answer.
Optimal Approach - Buckets as Wide as the Average Gap
Intuition
Make the buckets ⌈(hi − lo) / (n − 1)⌉ wide, the average gap rounded up, and put each value in bucket (v − lo) / width, rounded down. Two values in one bucket are less than the width apart, and the largest gap is at least the width, so the answer is always a jump from one non-empty bucket to the next. Each bucket only needs its smallest and largest value; empty buckets are skipped, and the jump spans them.
Step-by-Step Explanation
Let's trace nums = [9, 1, 2, 30, 26], where one bucket stays empty:
lo = 1,hi = 30, and the width is ⌈29 / 4⌉ = 8, so 4 buckets.- Each value goes in bucket
(v − lo) / width, rounded down: bucket 0 runs from 1 to 2, bucket 1 holds just 9, bucket 2 stays empty, bucket 3 runs from 26 to 30. - From bucket 0's largest, 2, to bucket 1's smallest, 9: 7.
- Bucket 2 is empty, so skip it.
- From bucket 1's largest, 9, to bucket 3's smallest, 26: 17.
- The largest jump, 17, is the answer: values in one bucket are less than 8 apart, and the largest gap is at least 8.
Buckets as Wide as the Average Gap — Each value dropped into its bucket, then the jumps between non-empty buckets.
Algorithm
- If there are fewer than two values, or they're all equal, return 0.
- Width = ⌈(hi − lo) / (n − 1)⌉, at least 1; there are ⌊(hi − lo) / width⌋ + 1 buckets.
- For each value, update its bucket's smallest and largest.
- Walk the buckets, skipping empty ones: each jump is this bucket's smallest minus the previous non-empty bucket's largest. Return the largest jump.
Code
class Solution {
public:
int maximumGap(vector<int>& nums) {
int n = nums.size();
if (n < 2) return 0;
int lo = *min_element(nums.begin(), nums.end()), hi = *max_element(nums.begin(), nums.end());
if (lo == hi) return 0;
long long width = max(1LL, ((long long) hi - lo + n - 2) / (n - 1)); // the average gap, rounded up
int count = (hi - lo) / width + 1;
vector<int> small(count, INT_MAX), big(count, INT_MIN);
for (int v : nums) {
int b = (v - lo) / width;
small[b] = min(small[b], v);
big[b] = max(big[b], v);
}
int best = 0, prev = big[0];
for (int b = 1; b < count; b++) {
if (small[b] == INT_MAX) continue; // an empty bucket: the gap spans it
best = max(best, small[b] - prev);
prev = big[b];
}
return best;
}
};
class Solution:
def maximumGap(self, nums: List[int]) -> int:
n = len(nums)
if n < 2:
return 0
lo, hi = min(nums), max(nums)
if lo == hi:
return 0
width = max(1, -(-(hi - lo) // (n - 1))) # the average gap, rounded up
count = (hi - lo) // width + 1
small, big = [None] * count, [None] * count
for v in nums:
b = (v - lo) // width
small[b] = v if small[b] is None else min(small[b], v)
big[b] = v if big[b] is None else max(big[b], v)
best, prev = 0, big[0]
for b in range(1, count):
if small[b] is None: # an empty bucket: the gap spans it
continue
best = max(best, small[b] - prev)
prev = big[b]
return best
class Solution {
public int maximumGap(int[] nums) {
int n = nums.length;
if (n < 2) return 0;
int lo = Integer.MAX_VALUE, hi = Integer.MIN_VALUE;
for (int v : nums) { lo = Math.min(lo, v); hi = Math.max(hi, v); }
if (lo == hi) return 0;
long width = Math.max(1L, ((long) hi - lo + n - 2) / (n - 1)); // the average gap, rounded up
int count = (int) ((hi - lo) / width) + 1;
int[] small = new int[count], big = new int[count];
java.util.Arrays.fill(small, Integer.MAX_VALUE);
java.util.Arrays.fill(big, Integer.MIN_VALUE);
for (int v : nums) {
int b = (int) ((v - lo) / width);
small[b] = Math.min(small[b], v);
big[b] = Math.max(big[b], v);
}
int best = 0, prev = big[0];
for (int b = 1; b < count; b++) {
if (small[b] == Integer.MAX_VALUE) continue; // an empty bucket: the gap spans it
best = Math.max(best, small[b] - prev);
prev = big[b];
}
return best;
}
}
var maximumGap = function(nums) {
const n = nums.length;
if (n < 2) return 0;
let lo = Infinity, hi = -Infinity;
for (const v of nums) { lo = Math.min(lo, v); hi = Math.max(hi, v); }
if (lo === hi) return 0;
const width = Math.max(1, Math.ceil((hi - lo) / (n - 1))); // the average gap, rounded up
const count = Math.floor((hi - lo) / width) + 1;
const small = new Array(count).fill(Infinity), big = new Array(count).fill(-Infinity);
for (const v of nums) {
const b = Math.floor((v - lo) / width);
small[b] = Math.min(small[b], v);
big[b] = Math.max(big[b], v);
}
let best = 0, prev = big[0];
for (let b = 1; b < count; b++) {
if (small[b] === Infinity) continue; // an empty bucket: the gap spans it
best = Math.max(best, small[b] - prev);
prev = big[b];
}
return best;
};
Complexity Analysis
Time Complexity: O(n)
One pass to find lo and hi, one to fill the buckets, one over at most n buckets.
Space Complexity: O(n)
Two numbers per bucket, at most n buckets.
Common Mistakes
Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.
Forgetting to sort. zip(nums, nums[1:])
On nums = [3, 6, 9, 1] it returns 8; the answer is 3. The gap is between neighbours in sorted order, not in the order given. Scanning the array as it comes measures jumps between values that aren't neighbours at all, like 9 to 1.
A bucket width of 0. width = (hi - lo) // (n - 1)
On nums = [1, 1, 2] it fails with ZeroDivisionError (integer division or modulo by zero) instead of returning 1. Rounding the average gap down gives 0 whenever hi − lo is smaller than n − 1, here 1 against 2, and dividing by the width fails. Round up, and keep the width at least 1.
Skipping the jump across empty buckets. small[b] - big[b - 1]
On nums = [0, 1, 2, 1000, 1001] it returns 0; the answer is 998. Comparing each bucket only with the one right before it misses a jump that spans empty buckets, and the largest gap can be exactly that jump: here 2 to 1000 runs from the first bucket to the last, over two empty ones.
Where This Pattern Is Taught
This problem practises buckets as wide as the average gap, so the largest gap falls between them. It's taught in Counting, Bucket and Radix Sort.