Question

Formatted question description: https://leetcode.ca/all/164.html

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 <= 10⁵
0 <= nums[i] <= 10⁹

Algorithm

Bucket Sort is employed here. Initially, identify the maximum and minimum values within the array. Subsequently, calculate the capacity of each bucket, which is determined by (maximum - minimum) / number + 1. To ascertain the required number of buckets, compute (maximum - minimum) / capacity of a bucket + 1.

Next, it’s essential to identify the local maximum and minimum within each bucket. Notably, the two numbers exhibiting the greatest distance will not reside within the same bucket. Instead, such a distance is observed between the minimum value of one bucket and the maximum value of another bucket. This observation is grounded in the principle that all numbers should be distributed across the buckets as evenly as possible, rather than clustering within a single bucket. This distribution strategy ensures that the maximum and minimum values are unlikely to be found in the same bucket.

Code

public class Maximum_Gap {

    public class Solution {
        public int maximumGap(int[] nums) {
            if (nums == null || nums.length <= 1) {
                return 0;
            }

            // Step 1: find max and min element
            int max = Integer.MIN_VALUE;
            int min = Integer.MAX_VALUE;
            for (int num : nums) {
                if (num > max) {
                    max = num;
                }

                if (num < min) {
                    min = num;
                }
            }

            int len = nums.length;

            // Step 2: calculate the intervals and number of buckets.
            int interval = (int) Math.ceil((double) (max - min) / (len - 1));

            if (interval == 0) {
                interval = 1;
            }
            int numBuckets = (max - min) / interval + 1;
            Bucket[] buckets = new Bucket[numBuckets];
            for (int i = 0; i < numBuckets; i++) {
                buckets[i] = new Bucket();
            }

            // Step 3: iterate through the nums and assign the number into the buckets.
            for (int num : nums) {
                int bucketNum = (num - min) / interval;
                if (num > buckets[bucketNum].max) {
                    buckets[bucketNum].max = num;
                }

                if (num < buckets[bucketNum].min) {
                    buckets[bucketNum].min = num;
                }
            }

            // Step 4: iterate through the buckets and get the maximal gap
            int prev = buckets[0].max;
            int maxGap = 0;
            for (int i = 1; i < numBuckets; i++) {
                if (prev != Integer.MIN_VALUE && buckets[i].min != Integer.MAX_VALUE) {
                    maxGap = Math.max(maxGap, buckets[i].min - prev);
                    prev = buckets[i].max;
                }
            }

            return maxGap;
        }

        private class Bucket {
            public int min;
            public int max;

            public Bucket() {
                min = Integer.MAX_VALUE;
                max = Integer.MIN_VALUE;
            }
        }
    }

}

//////

class Solution {
    public int maximumGap(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return 0;
        }
        int inf = 0x3f3f3f3f;
        int mi = inf, mx = -inf;
        for (int v : nums) {
            mi = Math.min(mi, v);
            mx = Math.max(mx, v);
        }
        int bucketSize = Math.max(1, (mx - mi) / (n - 1));
        int bucketCount = (mx - mi) / bucketSize + 1;
        int[][] buckets = new int[bucketCount][2];
        for (var bucket : buckets) {
            bucket[0] = inf;
            bucket[1] = -inf;
        }
        for (int v : nums) {
            int i = (v - mi) / bucketSize;
            buckets[i][0] = Math.min(buckets[i][0], v);
            buckets[i][1] = Math.max(buckets[i][1], v);
        }
        int prev = inf;
        int ans = 0;
        for (var bucket : buckets) {
            if (bucket[0] > bucket[1]) {
                continue;
            }
            ans = Math.max(ans, bucket[0] - prev);
            prev = bucket[1];
        }
        return ans;
    }
}

// OJ: https://leetcode.com/problems/maximum-gap/
// Time: O(N)
// Space: O(N)
// Ref: https://discuss.leetcode.com/topic/5999/bucket-sort-java-solution-with-explanation-o-n-time-and-space
class Solution {
public:
    int maximumGap(vector<int>& A) {
        if (A.size() == 1) return 0;
        int minVal = *min_element(begin(A), end(A));
        int maxVal = *max_element(begin(A), end(A));
        int N = A.size(), gap = (maxVal - minVal + N - 2) / (N - 1);
        vector<int> mn(N - 1, INT_MAX), mx(N - 1, INT_MIN);
        for (int n : A) {
            if (n == minVal || n == maxVal) continue;
            int i = (n - minVal) / gap;
            mn[i] = min(mn[i], n);
            mx[i] = max(mx[i], n);
        }
        int ans = gap, prev = minVal;
        for (int i = 0; i < N - 1; ++i) {
            if (mn[i] == INT_MAX) continue;
            ans = max(ans, mn[i] - prev);
            prev = mx[i];
        }
        return max(ans, maxVal - prev);
    }
};

'''
>>> math.inf
inf
>>> 1 + math.inf
inf
>>> -1 - math.inf
-inf
'''
class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 2:
            return 0
        mi, mx = min(nums), max(nums)
        # also passing OJ: 
        # bucket_size = max(1, (mx - mi) // (n - 1))
        bucket_size = max(1, (mx - mi) // n)
        bucket_count = (mx - mi) // bucket_size + 1
        buckets = [[inf, -inf] for _ in range(bucket_count)]
        for v in nums:
            i = (v - mi) // bucket_size
            buckets[i][0] = min(buckets[i][0], v)
            buckets[i][1] = max(buckets[i][1], v)
        ans = 0
        prev = inf
        for curmin, curmax in buckets:
            if curmin > curmax:
                continue
            ans = max(ans, curmin - prev)
            prev = curmax
        return ans

############

class Solution(object):
  def maximumGap(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    if len(nums) < 2:
      return 0
    a, b = min(nums), max(nums)
    if a == b:
      return 0
    ans = 0
    gap = int(math.ceil((b - a + 0.0) / (len(nums) - 1)))
    bucketMin = [None for _ in range(0, len(nums) + 1)]
    bucketMax = [None for _ in range(0, len(nums) + 1)]

    for num in nums:
      index = (num - a) / gap
      if bucketMin[index] is None:
        bucketMin[index] = num
      else:
        bucketMin[index] = min(bucketMin[index], num)
      if bucketMax[index] is None:
        bucketMax[index] = num
      else:
        bucketMax[index] = max(bucketMax[index], num)
    bucketMin = [b for b in bucketMin if b is not None]
    bucketMax = [b for b in bucketMax if b is not None]
    for i in range(0, len(bucketMin) - 1):
      ans = max(ans, bucketMin[i + 1] - bucketMax[i])
    return ans

func maximumGap(nums []int) int {
	n := len(nums)
	if n < 2 {
		return 0
	}
	inf := 0x3f3f3f3f
	mi, mx := inf, -inf
	for _, v := range nums {
		mi = min(mi, v)
		mx = max(mx, v)
	}
	bucketSize := max(1, (mx-mi)/(n-1))
	bucketCount := (mx-mi)/bucketSize + 1
	buckets := make([][]int, bucketCount)
	for i := range buckets {
		buckets[i] = []int{inf, -inf}
	}
	for _, v := range nums {
		i := (v - mi) / bucketSize
		buckets[i][0] = min(buckets[i][0], v)
		buckets[i][1] = max(buckets[i][1], v)
	}
	ans := 0
	prev := inf
	for _, bucket := range buckets {
		if bucket[0] > bucket[1] {
			continue
		}
		ans = max(ans, bucket[0]-prev)
		prev = bucket[1]
	}
	return ans
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

using System;
using System.Linq;

public class Solution {
    public int MaximumGap(int[] nums) {
        if (nums.Length < 2) return 0;
        var max = nums.Max();
        var min = nums.Min();
        var bucketSize = Math.Max(1, (max - min) / (nums.Length - 1));
        var buckets = new Tuple<int, int>[(max - min) / bucketSize + 1];
        foreach (var num in nums)
        {
            var index = (num - min) / bucketSize;
            if (buckets[index] == null)
            {
                buckets[index] = Tuple.Create(num, num);
            }
            else
            {
                buckets[index] = Tuple.Create(Math.Min(buckets[index].Item1, num), Math.Max(buckets[index].Item2, num));
            }
        }

        var result = 0;
        Tuple<int, int> lastBucket = null;
        for (var i = 0; i < buckets.Length; ++i)
        {
            if (buckets[i] != null)
            {
                if (lastBucket != null)
                {
                    result = Math.Max(result, buckets[i].Item1 - lastBucket.Item2);
                }
                lastBucket = buckets[i];
            }
        }
        return result;
    }
}

164 - Maximum Gap

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions