{x}
blog image

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

Solution Explanation for LeetCode 164: Maximum Gap

This problem asks to find the maximum difference between two successive elements in the sorted form of an integer array. The constraint mandates a linear time and space complexity solution. A naive sorting approach would exceed the time complexity requirement. The optimal solution uses a variation of bucket sort.

Approach: Bucket Sort

The core idea is to divide the input array's range into buckets. If the elements are evenly distributed, the maximum gap will likely be found between buckets. This approach leverages the fact that if we have n numbers and n-1 buckets, at least one bucket will be empty.

  1. Find Min and Max: Determine the minimum (min) and maximum (max) values in the input array nums. If the array has fewer than two elements, the maximum gap is 0.

  2. Calculate Bucket Size: Compute the size of each bucket using bucketSize = max(1, (max - min) / (n - 1)). This ensures at least one bucket per element, preventing division by zero.

  3. Create Buckets: Initialize an array of buckets. Each bucket stores a pair: the minimum and maximum values found within that bucket. We can use a 2D array or a data structure like pair or Tuple depending on the language. Initialize minimum values to infinity and maximum values to negative infinity.

  4. Populate Buckets: Iterate through the input array. For each element num, calculate its bucket index using index = (num - min) / bucketSize. Update the minimum and maximum values within that bucket accordingly.

  5. Find Maximum Gap: Iterate through the buckets. The maximum gap is the largest difference between the minimum of the current bucket and the maximum of the previous non-empty bucket.

Time and Space Complexity Analysis

  • Time Complexity: O(n). All steps, including finding min/max, calculating bucket size, populating buckets, and finding the maximum gap, take linear time with respect to the input array size n.

  • Space Complexity: O(n). The space used is dominated by the bucket array, which has a size proportional to n in the worst case (when the numbers are evenly distributed).

Code Implementation in Multiple Languages

The following code snippets implement the bucket sort approach in Python, Java, C++, Go, and C#. Note that the handling of buckets might vary slightly depending on the language's features (using pairs, tuples, or custom classes).

Python3:

class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 2:
            return 0
        mi, mx = min(nums), max(nums)
        bucket_size = max(1, (mx - mi) // (n - 1))
        bucket_count = (mx - mi) // bucket_size + 1
        buckets = [[float('inf'), float('-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 = float('-inf')
        for curmin, curmax in buckets:
            if curmin == float('inf'):
                continue
            ans = max(ans, curmin - prev)
            prev = curmax
        return ans

Java:

class Solution {
    public int maximumGap(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return 0;
        }
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for (int num : nums) {
            min = Math.min(min, num);
            max = Math.max(max, num);
        }
        int bucketSize = Math.max(1, (max - min) / (n - 1));
        int bucketCount = (max - min) / bucketSize + 1;
        int[][] buckets = new int[bucketCount][2];
        for (int i = 0; i < bucketCount; i++) {
            buckets[i][0] = Integer.MAX_VALUE;
            buckets[i][1] = Integer.MIN_VALUE;
        }
        for (int num : nums) {
            int index = (num - min) / bucketSize;
            buckets[index][0] = Math.min(buckets[index][0], num);
            buckets[index][1] = Math.max(buckets[index][1], num);
        }
        int maxGap = 0;
        int prevMax = Integer.MIN_VALUE;
        for (int[] bucket : buckets) {
            if (bucket[0] == Integer.MAX_VALUE) continue;
            maxGap = Math.max(maxGap, bucket[0] - prevMax);
            prevMax = bucket[1];
        }
        return maxGap;
    }
}

C++:

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) return 0;
        int minVal = *min_element(nums.begin(), nums.end());
        int maxVal = *max_element(nums.begin(), nums.end());
        int bucketSize = max(1, (maxVal - minVal) / (n - 1));
        int bucketCount = (maxVal - minVal) / bucketSize + 1;
        vector<pair<int, int>> buckets(bucketCount, {INT_MAX, INT_MIN});
        for (int num : nums) {
            int index = (num - minVal) / bucketSize;
            buckets[index].first = min(buckets[index].first, num);
            buckets[index].second = max(buckets[index].second, num);
        }
        int maxGap = 0;
        int prevMax = INT_MIN;
        for (auto& bucket : buckets) {
            if (bucket.first == INT_MAX) continue;
            maxGap = max(maxGap, bucket.first - prevMax);
            prevMax = bucket.second;
        }
        return maxGap;
    }
};

Go:

func maximumGap(nums []int) int {
	n := len(nums)
	if n < 2 {
		return 0
	}
	minVal, maxVal := nums[0], nums[0]
	for _, num := range nums {
		if num < minVal {
			minVal = num
		}
		if num > maxVal {
			maxVal = num
		}
	}
	bucketSize := max(1, (maxVal-minVal)/(n-1))
	bucketCount := (maxVal-minVal)/bucketSize + 1
	buckets := make([][2]int, bucketCount)
	for i := range buckets {
		buckets[i] = [2]int{math.MaxInt32, math.MinInt32}
	}
	for _, num := range nums {
		index := (num - minVal) / bucketSize
		buckets[index][0] = min(buckets[index][0], num)
		buckets[index][1] = max(buckets[index][1], num)
	}
	maxGap := 0
	prevMax := math.MinInt32
	for _, bucket := range buckets {
		if bucket[0] == math.MaxInt32 {
			continue
		}
		maxGap = max(maxGap, bucket[0]-prevMax)
		prevMax = bucket[1]
	}
	return maxGap
}
 
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
 
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

C#:

public class Solution {
    public int MaximumGap(int[] nums) {
        if (nums.Length < 2) return 0;
        int minVal = nums.Min();
        int maxVal = nums.Max();
        int bucketSize = Math.Max(1, (maxVal - minVal) / (nums.Length - 1));
        int bucketCount = (maxVal - minVal) / bucketSize + 1;
        Tuple<int, int>[] buckets = new Tuple<int, int>[bucketCount];
        for (int i = 0; i < bucketCount; i++) {
            buckets[i] = Tuple.Create(int.MaxValue, int.MinValue);
        }
        foreach (int num in nums) {
            int index = (num - minVal) / bucketSize;
            buckets[index] = Tuple.Create(Math.Min(buckets[index].Item1, num), Math.Max(buckets[index].Item2, num));
        }
        int maxGap = 0;
        int prevMax = int.MinValue;
        foreach (Tuple<int, int> bucket in buckets) {
            if (bucket.Item1 == int.MaxValue) continue;
            maxGap = Math.Max(maxGap, bucket.Item1 - prevMax);
            prevMax = bucket.Item2;
        }
        return maxGap;
    }
}

These code examples demonstrate the bucket sort approach, achieving linear time and space complexity as required. Remember to handle edge cases like empty or single-element arrays appropriately.