The "Maximum Gap" problem asks you to find the largest difference between any two successive elements in the sorted form of a given unsorted array of non-negative integers, nums. Specifically, after sorting nums in ascending order, you must determine the maximum value of nums[i] - nums[i - 1] for all valid indices i (where 1 ≤ i < n, and n is the length of nums).
0.
At first glance, the problem seems to require sorting the array and then finding the maximum difference between consecutive elements. This brute-force solution would take O(n \log n) time because of the sort operation. However, the problem explicitly demands a linear time solution.
To achieve O(n) time, we need to avoid general-purpose sorting. This leads us to consider bucket sort or radix sort, which can sort numbers in linear time under certain conditions. The key insight is that the maximum gap will not be within a bucket (since the bucket size is minimized), but rather between buckets. Thus, by distributing numbers into buckets and tracking the minimum and maximum of each bucket, we can compute the maximum gap efficiently.
The optimal solution uses a bucket-based approach inspired by the pigeonhole principle. Here are the step-by-step details:
n numbers, the maximum gap is at least ceil((max - min) / (n - 1)). This value is used as the bucket size.
n - 1 buckets, each able to store the minimum and maximum value that falls into that bucket.
(num - min) // bucket_size. Update the bucket's min and max accordingly.
This approach guarantees an O(n) time and space solution because each step (finding min/max, distributing, and scanning) takes linear time.
Let's walk through an example with nums = [3, 6, 9, 1]:
O(n \log n)O(n)O(n \log n) time, O(1) or O(n) space (depending on sort)O(n)O(n)O(n)O(n) time, O(n) space for bucketsThe optimized approach meets the problem's requirements for efficiency.
The "Maximum Gap" problem challenges us to find the largest difference between adjacent elements in a sorted version of an array, but under a strict linear time constraint. By leveraging the pigeonhole principle and using buckets to partition the value range, we efficiently compute the answer without explicit sorting. The solution is elegant because it transforms a seemingly sorting-dependent problem into a clever counting and partitioning exercise, making it both fast and memory-efficient.
from math import ceil
class Solution:
def maximumGap(self, nums):
if len(nums) < 2:
return 0
min_num, max_num = min(nums), max(nums)
if min_num == max_num:
return 0
n = len(nums)
bucket_size = ceil((max_num - min_num) / (n - 1))
bucket_count = n - 1
bucket_min = [float('inf')] * bucket_count
bucket_max = [float('-inf')] * bucket_count
for num in nums:
if num == min_num or num == max_num:
continue
idx = (num - min_num) // bucket_size
bucket_min[idx] = min(num, bucket_min[idx])
bucket_max[idx] = max(num, bucket_max[idx])
max_gap = 0
prev = min_num
for i in range(bucket_count):
if bucket_min[i] == float('inf'):
continue
max_gap = max(max_gap, bucket_min[i] - prev)
prev = bucket_max[i]
max_gap = max(max_gap, max_num - prev)
return max_gap
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
class Solution {
public:
int maximumGap(vector<int>& nums) {
int n = nums.size();
if (n < 2) return 0;
int min_num = *min_element(nums.begin(), nums.end());
int max_num = *max_element(nums.begin(), nums.end());
if (min_num == max_num) return 0;
int bucket_size = (max_num - min_num + n - 2) / (n - 1); // ceil
int bucket_count = n - 1;
vector<int> bucket_min(bucket_count, INT_MAX);
vector<int> bucket_max(bucket_count, INT_MIN);
for (int num : nums) {
if (num == min_num || num == max_num) continue;
int idx = (num - min_num) / bucket_size;
bucket_min[idx] = min(bucket_min[idx], num);
bucket_max[idx] = max(bucket_max[idx], num);
}
int max_gap = 0, prev = min_num;
for (int i = 0; i < bucket_count; ++i) {
if (bucket_min[i] == INT_MAX) continue;
max_gap = max(max_gap, bucket_min[i] - prev);
prev = bucket_max[i];
}
max_gap = max(max_gap, max_num - prev);
return max_gap;
}
};
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 num : nums) {
min = Math.min(min, num);
max = Math.max(max, num);
}
if (min == max) return 0;
int bucketSize = (int)Math.ceil((double)(max - min) / (n - 1));
int bucketCount = n - 1;
int[] bucketMin = new int[bucketCount];
int[] bucketMax = new int[bucketCount];
for (int i = 0; i < bucketCount; i++) {
bucketMin[i] = Integer.MAX_VALUE;
bucketMax[i] = Integer.MIN_VALUE;
}
for (int num : nums) {
if (num == min || num == max) continue;
int idx = (num - min) / bucketSize;
bucketMin[idx] = Math.min(bucketMin[idx], num);
bucketMax[idx] = Math.max(bucketMax[idx], num);
}
int maxGap = 0, prev = min;
for (int i = 0; i < bucketCount; i++) {
if (bucketMin[i] == Integer.MAX_VALUE) continue;
maxGap = Math.max(maxGap, bucketMin[i] - prev);
prev = bucketMax[i];
}
maxGap = Math.max(maxGap, max - prev);
return maxGap;
}
}
var maximumGap = function(nums) {
if (nums.length < 2) return 0;
let minNum = Math.min(...nums), maxNum = Math.max(...nums);
if (minNum === maxNum) return 0;
let n = nums.length;
let bucketSize = Math.ceil((maxNum - minNum) / (n - 1));
let bucketCount = n - 1;
let bucketMin = new Array(bucketCount).fill(Infinity);
let bucketMax = new Array(bucketCount).fill(-Infinity);
for (let num of nums) {
if (num === minNum || num === maxNum) continue;
let idx = Math.floor((num - minNum) / bucketSize);
bucketMin[idx] = Math.min(bucketMin[idx], num);
bucketMax[idx] = Math.max(bucketMax[idx], num);
}
let maxGap = 0, prev = minNum;
for (let i = 0; i < bucketCount; i++) {
if (bucketMin[i] === Infinity) continue;
maxGap = Math.max(maxGap, bucketMin[i] - prev);
prev = bucketMax[i];
}
maxGap = Math.max(maxGap, maxNum - prev);
return maxGap;
};