Maximum Gap Given an integer array nums
, return the maximum difference between two successive elements in its sorted form. If the array contains less than two elements, return 0
.
You must write an algorithm that runs in linear time and uses linear extra space.
Example 1:
Input: nums = [3,6,9,1] Output: 3 Explanation: The sorted form of the array is [1,3,6,9], either (3,6) or (6,9) has the maximum difference 3.
Example 2:
Input: nums = [10] Output: 0 Explanation: The array contains less than 2 elements, therefore return 0.
Constraints:
1 <= nums.length <= 105
0 <= nums[i] <= 109
Maximum Gap Solutions
✅Time:
✅Space:
C++
struct Bucket {
int min;
int max;
};
class Solution {
public:
int maximumGap(vector<int>& nums) {
if (nums.size() < 2)
return 0;
const int mini = *min_element(begin(nums), end(nums));
const int maxi = *max_element(begin(nums), end(nums));
if (mini == maxi)
return 0;
const int gap = ceil((maxi - mini) / (double)(nums.size() - 1));
const int bucketSize = (maxi - mini) / gap + 1;
vector<Bucket> buckets(bucketSize, {INT_MAX, INT_MIN});
for (const int num : nums) {
const int i = (num - mini) / gap;
buckets[i].min = min(buckets[i].min, num);
buckets[i].max = max(buckets[i].max, num);
}
int ans = 0;
int prevMax = mini;
for (const Bucket& bucket : buckets) {
if (bucket.min == INT_MAX)
continue; // empty bucket
ans = max(ans, bucket.min - prevMax);
prevMax = bucket.max;
}
return ans;
}
};
Java
class Bucket {
public int min;
public int max;
public Bucket(int min, int max) {
this.min = min;
this.max = max;
}
}
class Solution {
public int maximumGap(int[] nums) {
if (nums.length < 2)
return 0;
final int min = Arrays.stream(nums).min().getAsInt();
final int max = Arrays.stream(nums).max().getAsInt();
if (min == max)
return 0;
final int gap = (int) Math.ceil((double) (max - min) / (nums.length - 1));
final int bucketsLength = (max - min) / gap + 1;
Bucket[] buckets = new Bucket[bucketsLength];
for (int i = 0; i < buckets.length; ++i)
buckets[i] = new Bucket(Integer.MAX_VALUE, Integer.MIN_VALUE);
for (final int num : nums) {
final int i = (num - min) / gap;
buckets[i].min = Math.min(buckets[i].min, num);
buckets[i].max = Math.max(buckets[i].max, num);
}
int ans = 0;
int prevMax = min;
for (final Bucket bucket : buckets) {
if (bucket.min == Integer.MAX_VALUE) // empty bucket
continue;
ans = Math.max(ans, bucket.min - prevMax);
prevMax = bucket.max;
}
return ans;
}
}
Python
class Bucket:
def __init__(self, mini: int, maxi: int):
self.mini = mini
self.maxi = maxi
class Solution:
def maximumGap(self, nums: List[int]) -> int:
if len(nums) < 2:
return 0
mini = min(nums)
maxi = max(nums)
if mini == maxi:
return 0
gap = ceil((maxi - mini) / (len(nums) - 1))
bucketSize = (maxi - mini) // gap + 1
buckets = [Bucket(math.inf, -math.inf) for _ in range(bucketSize)]
for num in nums:
i = (num - mini) // gap
buckets[i].mini = min(buckets[i].mini, num)
buckets[i].maxi = max(buckets[i].maxi, num)
ans = 0
prevMax = mini
for bucket in buckets:
if bucket.mini == math.inf:
continue # empty bucket
ans = max(ans, bucket.mini - prevMax)
prevMax = bucket.maxi
return ans
Watch Tutorial
Checkout more Solutions here