Skip to content

164. Maximum Gap 👍

  • Time:
  • Space: 
 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
struct Bucket {
  int min;
  int max;
};

class Solution {
 public:
  int maximumGap(vector<int>& nums) {
    if (nums.size() < 2)
      return 0;

    const int mini = *min_element(begin(nums), end(nums));
    const int maxi = *max_element(begin(nums), end(nums));
    if (mini == maxi)
      return 0;

    const int gap = ceil((maxi - mini) / (double)(nums.size() - 1));
    const int bucketSize = (maxi - mini) / gap + 1;
    vector<Bucket> buckets(bucketSize, {INT_MAX, INT_MIN});

    for (const int num : nums) {
      const int i = (num - mini) / gap;
      buckets[i].min = min(buckets[i].min, num);
      buckets[i].max = max(buckets[i].max, num);
    }

    int ans = 0;
    int prevMax = mini;

    for (const Bucket& bucket : buckets) {
      if (bucket.min == INT_MAX)
        continue;  // Empty bucket
      ans = max(ans, bucket.min - prevMax);
      prevMax = bucket.max;
    }

    return ans;
  }
};

 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
class Bucket {
  public int min;
  public int max;
  public Bucket(int min, int max) {
    this.min = min;
    this.max = max;
  }
}

class Solution {
  public int maximumGap(int[] nums) {
    if (nums.length < 2)
      return 0;

    final int min = Arrays.stream(nums).min().getAsInt();
    final int max = Arrays.stream(nums).max().getAsInt();
    if (min == max)
      return 0;

    final int gap = (int) Math.ceil((double) (max - min) / (nums.length - 1));
    final int bucketsLength = (max - min) / gap + 1;
    Bucket[] buckets = new Bucket[bucketsLength];

    for (int i = 0; i < buckets.length; ++i)
      buckets[i] = new Bucket(Integer.MAX_VALUE, Integer.MIN_VALUE);

    for (final int num : nums) {
      final int i = (num - min) / gap;
      buckets[i].min = Math.min(buckets[i].min, num);
      buckets[i].max = Math.max(buckets[i].max, num);
    }

    int ans = 0;
    int prevMax = min;

    for (final Bucket bucket : buckets) {
      if (bucket.min == Integer.MAX_VALUE) // Empty bucket
        continue;
      ans = Math.max(ans, bucket.min - prevMax);
      prevMax = bucket.max;
    }

    return ans;
  }
}

 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
class Bucket:
  def __init__(self, mini: int, maxi: int):
    self.mini = mini
    self.maxi = maxi


class Solution:
  def maximumGap(self, nums: List[int]) -> int:
    if len(nums) < 2:
      return 0

    mini = min(nums)
    maxi = max(nums)
    if mini == maxi:
      return 0

    gap = math.ceil((maxi - mini) / (len(nums) - 1))
    bucketSize = (maxi - mini) // gap + 1
    buckets = [Bucket(math.inf, -math.inf) for _ in range(bucketSize)]

    for num in nums:
      i = (num - mini) // gap
      buckets[i].mini = min(buckets[i].mini, num)
      buckets[i].maxi = max(buckets[i].maxi, num)

    ans = 0
    prevMax = mini

    for bucket in buckets:
      if bucket.mini == math.inf:
        continue  # Empty bucket
      ans = max(ans, bucket.mini - prevMax)
      prevMax = bucket.maxi

    return ans