164. Maximum Gap
Explanation
To solve this problem in linear time and space, we can use the concept of bucket sort. The idea is to divide the range of the input numbers into N-1 buckets, where N is the number of elements in the input array. Then, we distribute the numbers into these buckets based on their value ranges. Finally, we calculate the maximum gap by comparing the minimum value of the next non-empty bucket with the maximum value of the previous non-empty bucket.
- Calculate the minimum and maximum values in the input array.
- Calculate the bucket size as (max - min) / (n - 1), where n is the number of elements in the input array.
- Initialize an array of buckets and distribute the numbers into the appropriate buckets.
- Iterate through the buckets to find the maximum gap between non-empty buckets.
Time Complexity: O(N)
Space Complexity: O(N)
class Solution {
public int maximumGap(int[] nums) {
if (nums == null || nums.length < 2) {
return 0;
}
int n = nums.length;
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
for (int num : nums) {
min = Math.min(min, num);
max = Math.max(max, num);
}
int bucketSize = Math.max(1, (max - min) / (n - 1));
int numBuckets = (max - min) / bucketSize + 1;
int[] minBucket = new int[numBuckets];
Arrays.fill(minBucket, Integer.MAX_VALUE);
int[] maxBucket = new int[numBuckets];
Arrays.fill(maxBucket, Integer.MIN_VALUE);
for (int num : nums) {
int idx = (num - min) / bucketSize;
minBucket[idx] = Math.min(minBucket[idx], num);
maxBucket[idx] = Math.max(maxBucket[idx], num);
}
int maxGap = 0, prevMax = min;
for (int i = 0; i < numBuckets; i++) {
if (minBucket[i] == Integer.MAX_VALUE || maxBucket[i] == Integer.MIN_VALUE)
continue;
maxGap = Math.max(maxGap, minBucket[i] - prevMax);
prevMax = maxBucket[i];
}
return maxGap;
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.