LeetCode - Maximum Gap
Problem description
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:
1
2
3
4
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:
1
2
3
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.
Analysis
The first thought is to use sorting and do a linear scan. However, if we need an O(n) algorithm, the bucket sort from LeetCode is applicable.
The general idea is to use multiply buckets to store the item, and make sure there’s one bucket is empty. So that the maximum gap is the one near the empty bucket.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public int maximumGap(int[] nums) {
if (nums == null || nums.length < 2){
return 0;
}
int len = nums.length;
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int i = 0;i < len ;i++){
min = Math.min(min, nums[i]);
max = Math.max(max,nums[i]);
}
// the minimum possibale gap, ceiling of the integer division
int gap = (int)Math.ceil((double)(max - min)/(len - 1));
int[] bucketsMIN = new int[len - 1]; // store the min value in that bucket
int[] bucketsMAX = new int[len - 1]; // store the max value in that bucket
Arrays.fill(bucketsMIN, Integer.MAX_VALUE);
Arrays.fill(bucketsMAX, Integer.MIN_VALUE);
// put numbers into buckets
for (int i:nums) {
if (i == min || i == max)
continue;
int idx = (i - min) / gap; // index of the right position in the buckets
bucketsMIN[idx] = Math.min(i, bucketsMIN[idx]);
bucketsMAX[idx] = Math.max(i, bucketsMAX[idx]);
}
// scan the buckets for the max gap
int maxGap = Integer.MIN_VALUE;
int previous = min;
for (int i = 0; i < len - 1; i++) {
if (bucketsMIN[i] == Integer.MAX_VALUE && bucketsMAX[i] == Integer.MIN_VALUE)
// empty bucket
continue;
// min value minus the previous value is the current gap
maxGap = Math.max(maxGap, bucketsMIN[i] - previous);
// update previous bucket value
previous = bucketsMAX[i];
}
maxGap = Math.max(maxGap, max - previous); // updata the final max value gap
return maxGap;
}
}