Leetcode 164. Maximum Gap

Problem Explanation

The problem is asking us to find the maximum difference between successive elements in the sorted list. If the list contains less than two elements, we should return 0 because we can't find any difference between elements in this case. If we have more than one element, we should sort the list first, then find the maximum difference between any two successive elements.

In most interview situations, sorting the list would be a simple approach. However, since the problem wants a solution that runs in linear time, a more efficient approach is needed.

As an example, consider the list [3,6,9,1]. If we sort this list, we get [1,3,6,9]. The gaps between the elements are 2 (between 1 and 3), 3 (between 3 and 6), and 3 (between 6 and 9). Thus, the maximum gap is 3.

Solution's Approach Explanation

The solution to this problem uses the concept of Bucket Sort. First, it finds the minimum and maximum values in the list. It then calculates the gap between each successive element in the sorted list. Using the minimum value, maximum value, and gap, it assigns elements in the list to different buckets.

Each bucket has a minimum and maximum value. As each element is visited, we calculate which bucket it fits into and set the minimum and maximum of that bucket accordingly. After all numbers are assigned to their respective buckets, we go through the buckets and compare the minimum of the current bucket with the maximum of the previous bucket to find the maximum gap.

Let's understand this better with a simple example:

Suppose we have the following array: nums = [3,6,9,1]

1. First, we calculate the minimum and maximum which will be 1 and 9.
2. Then, we calculate the gap which is ceil((maxi - mini) / (double)(nums.size() - 1)) which will be 3.
3. We then group the numbers to their respective buckets. We have two buckets and they look like this:

1
2
3  Bucket 1 : { min : 1, max : 3 }
4  Bucket 2 : { min : 6, max : 9 }

4. Finally, we iterate through the buckets and calculate the max difference. The maximum difference will be 6 - 3 = 3.

Python Solution

1
2python
3class Solution:
4    def maximumGap(self, nums):
5        if len(nums) < 2:
6            return 0
7
8        mini, maxi = min(nums), max(nums)
9        if mini == maxi:
10            return 0
11
12        gap = -(-maxi + mini) // (len(nums) - 1)
13        buckets = [[None, None] for _ in range((maxi-mini)//gap + 1)]
14        for num in nums:
15            b = (num-mini) // gap
16            if buckets[b][0] is None:
17                buckets[b][:] = [num, num]
18            else:
19                buckets[b][0] = min(buckets[b][0], num)
20                buckets[b][1] = max(buckets[b][1], num)
21        buckets = [b for b in buckets if b[0] is not None]
22        
23        return max(buckets[i][0]-buckets[i-1][1] for i in range(1, len(buckets)))

Java Solution

1
2java
3public class Solution {
4     public int maximumGap(int[] nums) {
5        if (nums.length < 2) return 0;
6        int min = nums[0], max = nums[0];
7        for (int i : nums) {
8            min = Math.min(min, i);
9            max = Math.max(max, i);
10        }
11        int gap = (int)Math.ceil((double)(max - min)/(nums.length - 1));
12        int[] bucketsMIN = new int[nums.length - 1];
13        int[] bucketsMAX = new int[nums.length - 1];
14        Arrays.fill(bucketsMIN, Integer.MAX_VALUE);
15        Arrays.fill(bucketsMAX, Integer.MIN_VALUE);
16        for (int i :nums) {
17            if (i == min || i == max)
18                continue;
19            int idx = (i - min) / gap;
20            bucketsMIN[idx] = Math.min(i, bucketsMIN[idx]);
21            bucketsMAX[idx] = Math.max(i, bucketsMAX[idx]);
22        }
23        int maxGap = Integer.MIN_VALUE;
24        int previous = min;
25        for (int i = 0; i < nums.length - 1; i++) {
26            if (bucketsMIN[i] == Integer.MAX_VALUE && bucketsMAX[i] == Integer.MIN_VALUE)
27                continue;
28            maxGap = Math.max(maxGap, bucketsMIN[i] - previous);
29            previous = bucketsMAX[i];
30        }
31        maxGap = Math.max(maxGap, max - previous);
32        return maxGap;
33    }
34}

JavaScript Solution

1
2javascript
3var maximumGap = function(nums) {
4    if (nums.length < 2) return 0;
5    let min = Math.min(...nums),
6        max = Math.max(...nums),
7        gap = Math.ceil((max - min) / (nums.length - 1)),
8        bucketsMIN = new Array(nums.length - 1).fill(Number.MAX_SAFE_INTEGER),
9        bucketsMAX = new Array(nums.length - 1).fill(Number.MIN_SAFE_INTEGER);
10    
11    for (let num of nums) {
12        if (num === min || num === max) continue;
13        let idx = Math.floor((num - min) / gap);
14        bucketsMIN[idx] = Math.min(num, bucketsMIN[idx]);
15        bucketsMAX[idx] = Math.max(num, bucketsMAX[idx]);
16    }
17    
18    let maxGap = -Infinity, pre = min;
19    
20    for (let i = 0; i < nums.length - 1; i++) {
21        if (bucketsMIN[i] === Number.MAX_SAFE_INTEGER && bucketsMAX[i] === Number.MIN_SAFE_INTEGER) continue;
22        maxGap = Math.max(maxGap, bucketsMIN[i] - pre);
23        pre = bucketsMAX[i];
24    }
25    
26    maxGap = Math.max(maxGap, max - pre);
27    
28    return maxGap;
29};

C++ Solution

1
2
3#include <bits/stdc++.h> 
4using namespace std; 
5
6class Solution {
7public:
8    int maximumGap(vector<int>& nums) {
9        if (nums.size() < 2)
10            return 0;
11
12        int mini = *min_element(nums.begin(), nums.end());
13        int maxi = *max_element(nums.begin(), nums.end());
14        if (mini == maxi)
15            return 0;
16
17        int gap = ceil((maxi - mini) / (double)(nums.size() - 1));
18        vector<pair<int, int>> buckets((maxi - mini) / gap + 1, {INT_MAX, INT_MIN});
19
20        for (const int num : nums) {
21            int i = (num - mini) / gap;
22            buckets[i].first = min(buckets[i].first, num);
23            buckets[i].second = max(buckets[i].second, num);
24        }
25
26        int ans = 0;
27        int prevMax = mini;
28        for (const auto &bucket : buckets) {
29            if (bucket.first == INT_MAX)
30                continue;
31            ans = max(ans, bucket.first - prevMax);
32            prevMax = bucket.second;
33        }
34
35        return ans;
36    }
37};

C# Solution

1
2
3public class Solution {
4    public int MaximumGap(int[] nums) {
5        if(nums.Length<2) return 0;
6        int min = nums.Min(), max = nums.Max(), gap = (int)Math.Ceiling((double)(max-min)/(nums.Length-1)), last = min;
7        int[] bucketsMin = new int[nums.Length-1];
8        int[] bucketsMax = new int[nums.Length-1];
9        for(int i=0; i<bucketsMin.Length; i++)  bucketsMin[i] = int.MaxValue;
10        for(int i=0; i<nums.Length; i++){
11            if(nums[i]==min || nums[i]==max) continue;
12            int idx = (nums[i]-min)/gap;
13            bucketsMin[idx] = Math.Min(bucketsMin[idx], nums[i]);
14            bucketsMax[idx] = Math.Max(bucketsMax[idx], nums[i]);
15        }
16        for(int i=0; i<bucketsMin.Length; i++){
17            if(bucketsMin[i]==int.MaxValue) continue;
18            gap = Math.Max(gap, bucketsMin[i]-last);
19            last = bucketsMax[i];
20        }
21        gap = Math.Max(gap, max-last);
22        return gap;
23    }
24}

In each of the explained solutions, it is evident that the underlying approach remains the same across all programming languages.

The problem is solved by using the bucket sort algorithm and finding the maximum gap between the minimum value of the current bucket and the maximum value of the previous bucket.

1. First, the program determines the maximum and minimum values present in the array. If the array has less than two integers or if the maximum and minimum values are equal, the program returns zero.

2. After finding the maximum and minimum values, the gap between them is divided by the array's total size, minus one. The balance is then round up to the next whole number. This gap is termed as the gap between the buckets.

3. An array of buckets that are used to store the maximum and minimum values of elements that belong in each bucket is then created.

4. While the entire array is traversed, each number is assigned to its corresponding bucket. If a bucket remains empty, it is skipped.

5. Once each integer is allocated a bucket, the maximum gap is then calculated. It is performed by comparing the difference between the maximum element value of the preceding bucket and the minimum element value of the succeeding bucket.

6. In the end, the maximum difference is returned to the user.

Keep in mind that no comparison is done inside a bucket. The gap found is the maximum possible gap in the sorted version of this array since all elements of a bucket are within the gap distance. Therefore, these solutions exemplify an ingenious application of the bucket sort algorithm.

In terms of complexity, all these solutions run in O(N) time where N is the number of elements in the input list. This is because each element is visited once when assigning elements to the buckets, and a second time when calculating the maximum gap. Thus, the time complexity is linear. In terms of space, all solutions also use O(N) space for storing the buckets.