164. Maximum Gap

  • 28.9%

https://leetcode.com/problems/maximum-gap/?tab=Description

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.


方法一:

类似于同排序 抽屉原则

https://discuss.leetcode.com/topic/13172/pigeon-hole-principle

Pigeon hole principle

Suppose you have n pigeons with labels and you put them into m holes based on their label with each hole of the same size. Why bother putting pigeons into holes? Because you want to disregard the distance between pigeons within each one hole.

Only when at least one hole is empty can we disregard the distance between pigeons within each one hole and compute the maximum gap solely by the distance between pigeons in adjacent holes. We make sure that at least one hole is empty by using m=n-1 (i.e. n-2 pigeons in n-1 holes => at least one hole is empty).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int maximumGap(vector<int>& nums) {
const int n = nums.size();
if(n<=1) return 0;
int maxE = *max_element(nums.begin(),nums.end());
int minE = *min_element(nums.begin(),nums.end());
double len = double(maxE-minE)/double(n-1);
vector<int> maxA(n,INT_MIN);
vector<int> minA(n,INT_MAX);
for(int i=0; i<n; i++) {
int index = (nums[i]-minE)/len;
maxA[index] = max(maxA[index],nums[i]);
minA[index] = min(minA[index],nums[i]);
}
int gap = 0, prev = maxA[0];
for(int i=1; i<n; i++) {
if(minA[i]==INT_MAX) continue;
gap = max(gap,minA[i]-prev);
prev = maxA[i];
}
return gap;
}

https://discuss.leetcode.com/topic/13172/pigeon-hole-principle/2

Great idea, get the essence of the problem. I’ll add some more explanations.

We divide the range of array into array.size() interval, where k = (maximum-minimum) / n.

[minimum, minimum + k), [minimum + k, minimum + 2k), … , [minimum + (n-1)k, maximum]

And we uses two extra array “max_in_interval” and “min_in_interval” to record the maximum and minimum of each interval.

First, let’s considering an uniformly distributed array of n numbers. By which I mean,

[minimum, minimum + k), [minimum + k, minimum + 2k), … , [minimum + (n-1)k, maximum]

n intervals each contains a single number. we could easily find the maximum gap by calculate min_in_interval[i+1] - max_in_interval[i]

Now comes the most important observation. If any single interval contains more than 1 number, then there must be an empty interval, and maximum gap is larger than a single interval. By which I mean if multiple numbers appear in the same interval, we can safely ignore the numbers which lies in the middle of interval(not max_in_interval nor min_in_interval).

Below comes my 16ms C++ AC solution.

This is a minor defeact in it, but the test case does not catch it. I uses INT_MAX as a sentinel which should fails if the input array contains it as an element.

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
int maximumGap(vector<int>& nums) {
if (nums.size() < 2)
return 0;

int max = *max_element(nums.begin(), nums.end());
int min = *min_element(nums.begin(), nums.end());

double interval_length = double(max - min) / nums.size();

vector<int> max_in_interval(nums.size(), INT_MIN);
vector<int> min_in_interval(nums.size(), INT_MAX);

for (auto &&each : nums) {
size_t index = (each - min) / interval_length; // auto ceiling
if (index == nums.size()) { // in considering of float-point number round up
index = nums.size() - 1;
}
if (max_in_interval[index] < each) {
max_in_interval[index] = each;
}
if (min_in_interval[index] > each) {
min_in_interval[index] = each;
}
}

int gap = 0;
int max_in_previous_interval = max_in_interval[0];
for (size_t i = 0; i < nums.size() - 1; ++i) {
if (min_in_interval[i + 1] == INT_MAX) { // skip the empty interval
continue;
}
else {
if (gap < min_in_interval[i + 1] - max_in_previous_interval) {
gap = min_in_interval[i + 1] - max_in_previous_interval;
}
max_in_previous_interval = max_in_interval[i + 1];
}
}
return gap;
}

https://discuss.leetcode.com/topic/9986/my-c-code-12-ms-bucket-sort-o-n-time-and-space

My C++ code (12 ms, “bucket sort”, O(n) time and space)

The key is to use the fact that the lower bound of the gap is (maxV - minV )/ (sSize - 1). With such in mind, we can put all the num elements into different bucket with size (maxV - minV )/ (sSize - 1) (please note when such size is less than 1, then use 1 instead) and in such way, we only need to consider the min and max of each bucket and don’t need to worry the numbers in between of each bucket since the gaps among those elements are smaller than the bucket size, and then the lower bound of the gap, so they can not achieve the max gap.

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
45
46
47
48
49
class Solution {
public:
int maximumGap(vector<int> &num) {
int sSize = num.size();
int i, res =0;
int minV, maxV;
int bucket_size, bucket_num, bucket_id;
int maxGap = INT_MIN;
int last_max;

if(sSize>1)
{
minV = maxV = num[0];
for(i=1; i<sSize; i++)
{
if(minV > num[i]) minV = num[i];
else if(maxV < num[i]) maxV = num[i];
}

bucket_size = max(1, (maxV - minV )/ (sSize - 1)));
bucket_num = (maxV - minV)/bucket_size + 1;

if(bucket_num <=1) return (maxV - minV);
vector<int> bucket_max(bucket_num, INT_MIN);
vector<int> bucket_min(bucket_num, INT_MAX);
vector<int> bucket_count(bucket_num, 0);

for(i=0; i<sSize; i++)
{
bucket_id = (num[i] - minV)/bucket_size;
bucket_count[bucket_id]++;
bucket_min[bucket_id] = bucket_min[bucket_id] > num[i]? num[i]:bucket_min[bucket_id];
bucket_max[bucket_id] = bucket_max[bucket_id] < num[i]? num[i]:bucket_max[bucket_id];
}

last_max = minV;
for(i=0; i<bucket_num; i++)
{
if(bucket_count[i]>0)
{
maxGap = max(maxGap, bucket_min[i]- last_max);
last_max = bucket_max[i];
}
}
return maxGap;
}
return 0;
}
};

https://discuss.leetcode.com/topic/5996/i-solved-it-using-radix-sort

I solved it using radix sort

Since linear time and space is required and all nums are non-negative, radix sort seems to be fit.
Here is the implementation.

Any better ideas?

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
class Solution:
# @param num, a list of integer
# @return an integer
def maximumGap(self, num):
if len(num) < 2:
return 0
num = self.radixSort(num)
res = 0
for i in range(1, len(num)):
res = max(num[i] - num[i - 1], res)
return res

def radixSort(self, num):
for i in range(31):
onebucket = []
zerobucket = []
needle = 1 << i
for j in range(len(num)):
if num[j] & needle != 0:
onebucket.append(num[j])
else:
zerobucket.append(num[j])
num = []
num += zerobucket
num += onebucket
return num

https://discuss.leetcode.com/topic/41228/beat-99-81-java-coder

Beat 99.81% java coder

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
public int maximumGap(int[] nums) {
int n = nums.length;
if(n < 2) return 0;
int min = nums[0];
int max = nums[0];
for(int i = 1;i < n;i++){
if(min > nums[i]) min = nums[i];
if(max < nums[i]) max = nums[i];
}

int gap = (max-min)/(n-1);
if(gap == 0) gap++;
int len = (max-min)/gap+1;
int [] tmax = new int [len];
int [] tmin = new int [len];

for(int i = 0;i < n;i++){
int index = (nums[i]-min)/gap;
if(nums[i] > tmax[index]) tmax[index] = nums[i];
if(tmin[index] == 0 || nums[i] < tmin[index]) tmin[index] = nums[i];
}
int myMax = 0;
for(int i = 0;i < len;i++){
if(myMax < tmin[i]-min) myMax = tmin[i]-min;
if(tmax[i] != 0) min = tmax[i];
}
return myMax;
}

https://discuss.leetcode.com/topic/21003/12ms-c-suggested-solution

12ms C++ Suggested Solution

This problem has a naive solution using sort and linear scan. The suggested solution uses the idea of bucket sort. The following is a C++ implementation of the suggested solution.

Suppose all the n elements in nums fall within [l, u], the maximum gap will not be smaller than gap = (u - l) / (n - 1). However, this gap may become 0 and so we take the maximum of it with 1 to guarantee that the gap used to create the buckets is meaningful.

Then there will be at most m = (u - l) / gap + 1 buckets. For each number num, it will fall in the k = (num - l) / gap bucket. After putting all elements of nums in the corresponding buckets, we can just scan the buckets to compute the maximum gap.

The maximum gap is only dependent on the maximum number of the current bucket and the minimum number of the next neighboring bucket (the bucket should not be empty). So we only store the minimum and the maximum of each bucket. Each bucket is initialized as {minimum = INT_MAX, maximum = INT_MIN} and then updated while updating the buckets.

Putting these together, we can have the following solution, barely a straight-forward implementation of the suggested solution.

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
class Solution {
public:
int maximumGap(vector<int>& nums) {
int n = nums.size();
if (n < 2) return 0;
auto lu = minmax_element(nums.begin(), nums.end());
int l = *lu.first, u = *lu.second;
int gap = max((u - l) / (n - 1), 1);
int m = (u - l) / gap + 1;
vector<int> bucketsMin(m, INT_MAX);
vector<int> bucketsMax(m, INT_MIN);
for (int num : nums) {
int k = (num - l) / gap;
if (num < bucketsMin[k]) bucketsMin[k] = num;
if (num > bucketsMax[k]) bucketsMax[k] = num;
}
int i = 0, j;
gap = bucketsMax[0] - bucketsMin[0];
while (i < m) {
j = i + 1;
while (j < m && bucketsMin[j] == INT_MAX && bucketsMax[j] == INT_MIN)
j++;
if (j == m) break;
gap = max(gap, bucketsMin[j] - bucketsMax[i]);
i = j;
}
return gap;
}
};

https://discuss.leetcode.com/topic/34414/clean-c-implementation-of-3-linear-time-sort-alg-with-detailed-explaination

Clean C++ implementation of 3 linear-time-sort-alg with detailed explaination

As we can see, we should grasp all the 3 typical linear-time-sorting algorithm implementation.
All the following 3 implementations have been modified from the GeeksForGeeks.
I have change the counting sort implementation to support negative numbers.
And the bucket support any float array input.

counting sort [ stable ] [ support:+/- intergers ]

radix sort [ use counting sort as sub-routine] [ support only
positive intergers]

bucket sort [support float : we need to change the array to in the
range [0, 1) ]

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/* counting sort Time O(N) Space O(N+range) */
/*
support : positive / negative arrays
the last travese the array X :
FORWARD->not stable
BACKWARD->stable
*/
void countingSort(vector<int>& X){
int len = X.size();
int start = INT_MAX, end = INT_MIN;
for (int i = 0; i < len; i++){
start = min(start, X[i]);
end = max(end, X[i]);
}
int range = end - start + 1;
vector<int> count(range, 0);
vector<int> result(len, 0);
for (int i = 0; i < len; i++){
count[X[i]-start]++;
}
for (int i = 1; i < range; i++){
count[i]=count[i-1]+count[i];
}
//for-ward traverse is not stable sorting
//for (int i = 0; i < len; i++)
//back-ward traverse is stable sorting
for (int i = len-1; i >= 0; i--){
//as we know that the count array recorded element should '-1' to get the index
result[count[X[i] - start]-1] = X[i];
count[X[i] - start]--;
}
for (int i = 0; i < len; i++){
X[i] = result[i];
}
}
/* Radix sort Time O(log(base,MAX)*(N+base)) Space O(constant) default:base=10 */
/*
support : only positive interger
can only deal with positive integers or change the float number
of the specified precision to intergers by multiplying 10^n
*/
void countingSort(vector<int>& X, int exp, int base){
int len = X.size();
int start = INT_MAX, end = INT_MIN;
for (int i = 0; i < len; i++){
start = min(start, (X[i] / exp)%base);
end = max(end, (X[i] / exp) % base);
}
int range = end - start + 1;
vector<int> count(range, 0);
vector<int> result(len, 0);
for (int i = 0; i < len; i++){
count[(X[i] / exp) % base -start]++;
}
for (int i = 1; i < range; i++){
count[i] = count[i - 1] + count[i];
}
//back-ward traverse is stable sorting
for (int i = len - 1; i >= 0; i--){
//as we know that the count array recorded element should '-1' to get the index
result[count[(X[i] / exp) % base -start] - 1] = X[i];
count[(X[i] / exp) % base - start]--;
}
for (int i = 0; i < len; i++){
X[i] = result[i];
}
}

void radixSort(vector<int> &X){
int len = X.size();
int max_val = INT_MIN;
int base = 10;
for (int i = 0; i < len; i++) max_val = max(X[i], max_val);
for (int exp = 1; max_val / exp>0; exp *= base){
countingSort(X, exp, base);
}
}
/* bubble sort Time Space */
/*
support : any float & int numbers
sort a large set of floating nubmers in range from 0.0 to 1.0
uniformly distributed across the range
the key idea is :
the insertion sort for all individual bucket is O(N)
*/
void bucketSort(vector<float>& X){
int len = X.size();
float max_val = X[0], min_val = X[0];;
for (int i = 1; i < len; i++) {
max_val = max(max_val, X[i]);
min_val = min(min_val, X[i]);
}
max_val++;

vector<vector<float>> bucket(len, vector<float>());
for (int i = 0; i < len; i++){
int index = len*(X[i]-min_val)/(max_val-min_val);
bucket[index].push_back(X[i]);
}

for (int i = 0; i < len; i++) sort(bucket[i].begin(), bucket[i].end());

int index = 0;
for (int i = 0; i < len; i++)
for (int j = 0; j < bucket[i].size(); j++)
X[index++] = bucket[i][j];
}
/* test all the 3-linear-sorting-implementation */
int main(){
vector<int> test1 = { 11, -200, 14, -2000, 30, 400, 10, 22, 456 };
countingSort(test1);
cout << endl<<"counting Sort result: ";
for (int i = 0; i < test1.size(); i++) cout << test1[i] <<" - ";
vector<int> test2 = { 11, 200, 14, 2000, 30, 400, 10, 22, 456 };
radixSort(test2);
cout << endl << "radix Sort result: ";
for (int i = 0; i < test2.size(); i++) cout << test2[i] << " - ";
vector<float> test3 = { 11, -200, 14, -2000, 30, 400, 10, 22, 456 };
bucketSort(test3);
cout << endl << "bucket Sort result: ";
for (int i = 0; i < test3.size(); i++) cout << test3[i] << " - ";
return 0;
}

https://discuss.leetcode.com/topic/14353/my-concise-and-short-c-code-with-comment-explanation

My concise and short c++ code with comment explanation

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
int maximumGap(vector<int>& nums) {
int n = nums.size();
if( n < 2 ) return 0;
int maxE = *max_element(nums.begin(),nums.end());
int minE = *min_element(nums.begin(),nums.end());

int len = maxE - minE;
if( len <= 1 ) return len;
vector<int> buck_max(n, INT_MIN);
vector<int> buck_min(n, INT_MAX);

for(int i = 0; i < n; i++) {
// note the divide and multiply order and the double cast
// it's used to avoid the overflow and underflow during calculation
int index = (double)( nums[i] - minE ) / len * ( n - 1 );
buck_max[index] = max(buck_max[index], nums[i]);
buck_min[index] = min(buck_min[index], nums[i]);
}

int gap = 0, pre = buck_max[0];
for(int i = 1; i < n; i++) {
if( buck_max[i] == INT_MIN ) continue;
gap = max(gap, buck_min[i] - pre);
pre = buck_max[i];
}
return gap;
}

https://discuss.leetcode.com/topic/5999/bucket-sort-java-solution-with-explanation-o-n-time-and-space

[bucket sort] JAVA solution with explanation, O(N) time and space

Suppose there are N elements in the array, the min value is min and the max value is max. Then the maximum gap will be no smaller than ceiling[(max - min ) / (N - 1)].

Let gap = ceiling[(max - min ) / (N - 1)]. We divide all numbers in the array into n-1 buckets, where k-th bucket contains all numbers in [min + (k-1)gap, min + k*gap). Since there are n-2 numbers that are not equal min or max and there are n-1 buckets, at least one of the buckets are empty. We only need to store the largest number and the smallest number in each bucket.

After we put all the numbers into the buckets. We can scan the buckets sequentially and get the max gap.
my blog for this problem

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
public class Solution {
public int maximumGap(int[] num) {
if (num == null || num.length < 2)
return 0;
// get the max and min value of the array
int min = num[0];
int max = num[0];
for (int i:num) {
min = Math.min(min, i);
max = Math.max(max, i);
}
// the minimum possibale gap, ceiling of the integer division
int gap = (int)Math.ceil((double)(max - min)/(num.length - 1));
int[] bucketsMIN = new int[num.length - 1]; // store the min value in that bucket
int[] bucketsMAX = new int[num.length - 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:num) {
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 < num.length - 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;
}
}

https://discuss.leetcode.com/topic/22221/radix-sort-solution-in-java-with-explanation

Radix sort solution in Java with explanation

You can look at radix sort visualization here before reading the code:

https://www.cs.usfca.edu/~galles/visualization/RadixSort.html

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
45
46
public class Solution {
public int maximumGap(int[] nums) {
if (nums == null || nums.length < 2) {
return 0;
}

// m is the maximal number in nums
int m = nums[0];
for (int i = 1; i < nums.length; i++) {
m = Math.max(m, nums[i]);
}

int exp = 1; // 1, 10, 100, 1000 ...
int R = 10; // 10 digits

int[] aux = new int[nums.length];

while (m / exp > 0) { // Go through all digits from LSB to MSB
int[] count = new int[R];

for (int i = 0; i < nums.length; i++) {
count[(nums[i] / exp) % 10]++;
}

for (int i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}

for (int i = nums.length - 1; i >= 0; i--) {
aux[--count[(nums[i] / exp) % 10]] = nums[i];
}

for (int i = 0; i < nums.length; i++) {
nums[i] = aux[i];
}
exp *= 10;
}

int max = 0;
for (int i = 1; i < aux.length; i++) {
max = Math.max(max, aux[i] - aux[i - 1]);
}

return max;
}
}
  1. The first step is to find the maximum value in nums array, it will be the threshold to end while loop.
  2. Then use the radix sort algorithm to sort based on each digit from Least Significant Bit (LSB) to Most Significant Bit (MSB), that’s exactly what’s showing in the link.
  3. (nums[i] / exp) % 10 is used to get the digit, for each digit, basically the digit itself serves as the index to access the count array. Count array stores the index to access aux array which stores the numbers after sorting based on the current digit.
  4. Finally, find the maximum gap from sorted array.

Time and space complexities are both O(n). (Actually time is O(10n) at worst case for Integer.MAX_VALUE 2147483647)

谢谢你,可爱的朋友。