Maximum Gap LeetCode Solution | Easy Approach

Maximum Gap Given an integer array nums, return the maximum difference between two successive elements in its sorted form. If the array contains less than two elements, return 0.

You must write an algorithm that runs in linear time and uses linear extra space.

Example 1:

Input: nums = [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:

Input: nums = [10]
Output: 0
Explanation: The array contains less than 2 elements, therefore return 0.

Constraints:

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 109

Maximum Gap Solutions

✅Time: 
✅Space:

C++

 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;
  }
};

Java

 
 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;
  }
}

Python

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 = 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

Watch Tutorial

Checkout more Solutions here