# Maximum Gap

`O(n)`

Sort

The problem requires `O(n)`

time complexity, and it looks something like sort.
Bucket Sort and Radix sort
are the two well known `O(n)`

sort.

Maybe an `O(32n)`

radix sort will work well.

## Bucket sort version

First, I choose N buckets and divide nums into [0, avg) [avg, 2avg) .... [navg, inf) and do a regular bucket sort. Through, this solution got accepted by leetcode, I found there is a better solution.

the most ideal gap is `max - min`

. so if there is `N`

elements, there will be `N - 1`

gaps,
the `maximum gap`

must be greater than `(max - min) / (N - 1)`

.

Like bucket sort, we put nums into `(max - min) / (max_gap) + 1`

buckets,
but, this time a good news is that we do not need to sort the numbers in the buckets,
what we need is only to remember the max and min of the bucket.
The reason is easy to understand: the number between the max and min of the bucket will not yield a bigger gap.

after bucketing, numbers are like

```
[MIN] [MIN] [MIN]
[ ] [ ] ... [ ]
[MAX] [MAX] [MAX]
```

The work left is to measure the gap between `bucket[i - 1].max`

and `bucket[i].min`

.

Note: the will be some emtpy buckets, skip them.

### Source code *Read on Github*

```
1 public class Solution {
2
3 static class Bucket {
4 int min = Integer.MAX_VALUE;
5 int max = Integer.MIN_VALUE;
6
7 void add(int n){
8 min = Math.min(n, min);
9 max = Math.max(n, max);
10 }
11 }
12
13 public int maximumGap(int[] num) {
14 if (num.length < 2) return 0;
15
16 int max = Integer.MIN_VALUE;
17 int min = Integer.MAX_VALUE;
18
19 for(int i = 0; i < num.length; i++){
20 max = Math.max(max, num[i]);
21 min = Math.min(min, num[i]);
22 }
23
24
25 int gap = (int) Math.ceil((double)(max - min) / (num.length - 1));
26 int n = (max - min) / gap + 1;
27
28 Bucket[] buckets = new Bucket[n];
29
30 for(int i = 0; i < num.length; i++){
31 int index = (num[i] - min) / gap;
32
33 if(buckets[index] == null) buckets[index] = new Bucket();
34
35 buckets[index].add(num[i]);
36 }
37
38 int maxGap = Integer.MIN_VALUE;
39
40 int prev = min;
41
42 for(int i = 0; i < buckets.length; i++){
43 if(buckets[i] == null) continue;
44
45 maxGap = Math.max(maxGap, buckets[i].min - prev);
46
47 prev = buckets[i].max;
48 }
49
50 return maxGap;
51 }
52 }
```