Given an unsorted array, find the maximum difference between the successive elements in its sorted form.
Return 0 if the array contains less than 2 elements.
Example 1:
Input: [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: [10]
Output: 0
Explanation: The array contains less than 2 elements, therefore return 0.
Note:
You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.
Try to solve it in linear time/space.
Solution:
class Solution {
public int maximumGap(int[] nums) {
int n = nums.length;
if (n <= 1) return 0;
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int val : nums) {
max = Math.max(max, val);
min = Math.min(min, val);
}
float gap = (max - min) / (float) (n - 1);
int[][] buckets = new int[n - 1][2];
for (int i = 0; i < n - 1; i ++) {
buckets[i][0] = Integer.MAX_VALUE;
buckets[i][1] = Integer.MIN_VALUE;
}
for (int val : nums) {
// max does not fit in buckets by definition
if (val == max) continue;
int b = (int) Math.floor((val - min) / gap);
buckets[b][0] = Math.min(buckets[b][0], val);
buckets[b][1] = Math.max(buckets[b][1], val);
}
// for (int[] arr: buckets) System.out.println(Arrays.toString(arr));
int maxGap = 0, prevMax = Integer.MIN_VALUE;
for (int i = 0; i < n - 1; i ++) {
int currMin = buckets[i][0];
if (currMin != Integer.MAX_VALUE && prevMax != Integer.MIN_VALUE) {
maxGap = Math.max(maxGap, currMin - prevMax);
}
if (buckets[i][1] != Integer.MIN_VALUE) {
prevMax = buckets[i][1];
}
}
maxGap = Math.max(maxGap, max - prevMax);
return maxGap;
}
}