164. Maximum Gap LeetCode Solution

In this guide, you will get 164. Maximum Gap LeetCode Solution with the best time and space complexity. The solution to Maximum Gap problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Maximum Gap solution in C++
Maximum Gap solution in Java
Maximum Gap solution in Python
Additional Resources

164. Maximum Gap LeetCode Solution image

Problem Statement of 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

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

164. Maximum Gap LeetCode Solution in C++

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;
  }
};
/* code provided by PROGIEZ */

164. Maximum Gap LeetCode Solution in Java

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;
  }
}
// code provided by PROGIEZ

164. Maximum Gap LeetCode Solution in Python

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
 # code by PROGIEZ