Skip to content

164. Maximum Gap 👍

  • Time: $O(n)$
  • Space: $O(n)$
 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 mn;
  int mx;
};

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

    const int mn = ranges::min(nums);
    const int mx = ranges::max(nums);
    if (mn == mx)
      return 0;

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

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

    int ans = 0;
    int prevMax = mn;

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

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

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

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

    final int gap = (int) Math.ceil((double) (mx - mn) / (nums.length - 1));
    final int bucketsLength = (mx - mn) / 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 - mn) / gap;
      buckets[i].mn = Math.min(buckets[i].mn, num);
      buckets[i].mx = Math.max(buckets[i].mx, num);
    }

    int ans = 0;
    int prevMax = mn;

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

    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, mn: int, mx: int):
    self.mn = mn
    self.mx = mx


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

    mn = min(nums)
    mx = max(nums)
    if mn == mx:
      return 0

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

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

    ans = 0
    prevMax = mn

    for bucket in buckets:
      if bucket.mn == math.inf:
        continue  # empty bucket
      ans = max(ans, bucket.mn - prevMax)
      prevMax = bucket.mx

    return ans