164. Maximum Gap

MediumArrayBucket SortRadix SortSorting

Problem Description

Given an array of integers, the task is to find the maximum difference between two successive elements after the array has been sorted. If an array has fewer than two elements, the maximum difference is defined to be 0. The challenge lies in doing this efficiently—in linear time (O(n)) and with linear extra space—which implies that the typical O(n log n) sorting algorithms like QuickSort or MergeSort can't be used directly.

This problem tests the ability to think beyond conventional sorting and to use other properties of the integers, such as their range and distribution, to find a more efficient solution.

Intuition

The key to solving this problem in linear time and space lies in using the fact that the range of the elements can be divided into intervals (or "buckets") such that if the maximum difference lies within a bucket, it does not surpass the bucket size. Understanding this principle helps to illuminate why a bucket sort-inspired approach can be effective.

The intuition for the solution involves several key insights:

The bucket size can be chosen such that we only need to check the gaps between adjacent buckets, not within them. This is because the minimum possible gap between the largest and smallest elements within a single bucket is smaller than the maximum gap we're searching for across the entire array.
Each bucket represents a subinterval of possible element values and needs to only store the minimum and maximum elements that fall into it.
We calculate the bucket size based on the range (difference between the maximum and minimum values) divided by the number of intervals, which equals the number of elements minus one.
We calculate the number of buckets based on the range divided by the bucket size.
By iterating through the array, we place each element into the appropriate bucket and record the minimum and maximum for that bucket.
To find the maximum gap, we look at the difference between the maximum of one bucket and the minimum of the next bucket which contains at least one element.
We skip any buckets that don't contain any elements.

This algorithm ensures that we don't need to perform a full sort of the elements and allows us to find the maximum gap in linear time. The space used is linear as well, depending on the range of input values and the number of elements in the array.

Learn more about Sorting patterns.

Solution Approach

The solution provided employs a bucket sort mechanism and careful analysis to achieve the goal of finding the maximum gap in linear time. Here is a step-by-step explanation of how the implementation works:

Initial Checks: The code begins by checking if the array nums has less than two elements. If so, the function immediately returns 0 because there can't be any gap with less than two values.
Minimum and Maximum Elements: Next, we calculate the minimum (mi) and maximum (mx) values in the array. These values are used to determine the range of nums and how to distribute the values into buckets.
Bucket Size and Count: We calculate the bucket size as the maximum of 1 and (mx - mi) // (n - 1), ensuring that it's at least 1. The bucket size is essentially the lower bound on the size of the maximum gap. The number of buckets is then the range divided by the bucket size, rounded up.
Bucket Initialization: Buckets are set up to track the minimum and maximum of each bucket; they are initialized with inf and -inf, respectively. This ensures we can later update them easily with the actual minimum and maximum values that fit into each bucket.
Distributing Elements into Buckets: The elements of the array are iterated over, with each element assigned to a bucket determined by (v - mi) // bucket_size. Within each bucket, we update the minimum and maximum values.
Finding the Maximum Gap: We initiate a variable prev as inf and start examining the buckets. For each bucket, if the current minimum and maximum indicate the bucket is not empty, we calculate the gap between the curmin of the current bucket and the prev (which is the curmax of the previous non-empty bucket). We update ans with the maximum of its current value and this new gap.
Result: After looping through all the buckets, the variable ans holds the maximum gap, which is returned as the final result.

This algorithm uses the properties of buckets to ensure that the eventual gap will be found between the buckets rather than within them, thus avoiding the need for a full sort and allowing us to keep to O(n) time complexity. The extra space is used efficiently, with a linear relationship to the number of elements in the array since we are creating a limited number of buckets based on these elements.

In terms of data structures, a list of lists is used to represent the buckets, and operations like min() and max() are used to maintain the bucket minimum and maximum values. The overall pattern is similar to bucket sort, but instead of sorting, we use the buckets to determine the maximum gap directly.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider an example to illustrate the solution approach:

Suppose we have an array nums with the following integers: [3, 6, 9, 1, 4]

Initial Checks: nums has more than two elements, so we proceed.
Minimum and Maximum Elements: The minimum value mi is 1 and the maximum value mx is 9.
Bucket Size and Count: With n = 5 elements, the bucket size is calculated as a maximum of 1 and (9 - 1) // (5 - 1) which is 2. There will be ⌈(9 - 1) / 2⌉ = 4 buckets to cover the range from 1 to 9.

Bucket Initialization: We create 4 buckets, each initialized to have a minimum (curmin) of infinity and a maximum (curmax) of -infinity:

Buckets: [[inf, -inf], [inf, -inf], [inf, -inf], [inf, -inf]]

Distributing Elements into Buckets: Now we place each element into the appropriate bucket based on the formula (v - mi) // bucket_size:
- 3 goes into bucket 1 ((3 - 1) // 2), updating curmin and curmax to 3.
- 6 goes into bucket 2 ((6 - 1) // 2), updating curmin and curmax to 6.
- 9 goes into bucket 4 ((9 - 1) // 2), since this is the last bucket, it simply updates curmin and curmax to 9.
- 1 goes into bucket 0 ((1 - 1) // 2), updating curmin and curmax to 1.
- 4 goes into bucket 1 ((4 - 1) // 2), updating curmin to 3 if necessary and curmax to 4.
The buckets now look like:
```
Buckets: [[1, 1], [3, 4], [6, 6], [inf, -inf], [9, 9]]
```
Finding the Maximum Gap: We set prev to 1 (the maximum of the first bucket, bucket 0). Then, we calculate the gaps:
- The gap between buckets 0 and 1 is 3 - 1 = 2.
- The gap between buckets 1 and 2 is 6 - 4 = 2.
- Bucket 3 is empty (still inf, -inf), so we skip it.
- The gap between buckets 2 and 4 is 9 - 6 = 3.
Therefore, the maximum gap we've found is 3.
Result: The final answer, which is the maximum gap after sorting the array, is 3.

This example demonstrates that by using the bucketing method, we can efficiently find the maximum gap without having to perform a complete sort of the original array. The linear time complexity (O(n)) is achieved because we processed each element only once to place it into a bucket, and then only needed to compare adjacent buckets for the maximum gap. The extra space used was linear in relation to the array size, which is also the number of buckets we initialized.

Solution Implementation

1from math import inf
2
3class Solution:
4    def maximumGap(self, nums):
5        # Get the length of the list
6        num_elements = len(nums)
7
8        # If there are less than 2 elements, the maximum gap is 0
9        if num_elements < 2:
10            return 0
11
12        # Calculate minimum and maximum value in the list
13        min_val, max_val = min(nums), max(nums)
14
15        # Calculate the bucket size, it should be at least 1
16        bucket_size = max(1, (max_val - min_val) // (num_elements - 1))
17      
18        # Calculate the number of buckets needed
19        bucket_count = (max_val - min_val) // bucket_size + 1
20      
21        # Create buckets, each bucket with a pair of values: [min_val_of_bucket, max_val_of_bucket]
22        buckets = [[inf, -inf] for _ in range(bucket_count)]
23      
24        # Place each number in its respective bucket
25        for value in nums:
26            bucket_index = (value - min_val) // bucket_size
27            buckets[bucket_index][0] = min(buckets[bucket_index][0], value)
28            buckets[bucket_index][1] = max(buckets[bucket_index][1], value)
29          
30        # Initialize the answer variable that will store the maximum gap
31        max_gap = 0
32
33        # Initialize the variable that keeps track of the previous bucket's maximum value
34        previous_max = inf
35
36        # Iterate through the buckets to find the maximum gap
37        for current_min, current_max in buckets:
38            # Skip the bucket if it is empty
39            if current_min > current_max:
40                continue
41
42            # The gap is the difference between the current bucket's min and the previous bucket's max
43            max_gap = max(max_gap, current_min - previous_max)
44          
45            # Update the previous bucket max for the next iteration
46            previous_max = current_max
47      
48        # Return the maximum gap found
49        return max_gap
50
51# Example usage:
52# sol = Solution()
53# print(sol.maximumGap([3, 6, 9, 1])) # Output: 3
54

1class Solution {
2    public int maximumGap(int[] nums) {
3        // Base case: if there are fewer than 2 elements, the maximum gap is 0
4        int n = nums.length;
5        if (n < 2) {
6            return 0;
7        }
8      
9        // Initialize minimum and maximum values to extreme values
10        int minVal = Integer.MAX_VALUE;
11        int maxVal = -Integer.MAX_VALUE;
12      
13        // Find the actual minimum and maximum values in the array
14        for (int v : nums) {
15            minVal = Math.min(minVal, v);
16            maxVal = Math.max(maxVal, v);
17        }
18      
19        // Determine the size of each bucket by using the range of numbers and number of elements
20        int bucketSize = Math.max(1, (maxVal - minVal) / (n - 1));
21        int bucketCount = (maxVal - minVal) / bucketSize + 1;
22      
23        // Initialize buckets to store the possible minimum and maximum values within each bucket
24        int[][] buckets = new int[bucketCount][2];
25        for (int[] bucket : buckets) {
26            bucket[0] = Integer.MAX_VALUE; // Minimum value in a bucket initialized to max value
27            bucket[1] = -Integer.MAX_VALUE; // Maximum value in a bucket initialized to min value
28        }
29      
30        // Place all numbers into buckets
31        for (int v : nums) {
32            int idx = (v - minVal) / bucketSize;
33            buckets[idx][0] = Math.min(buckets[idx][0], v); // Update bucket minimum
34            buckets[idx][1] = Math.max(buckets[idx][1], v); // Update bucket maximum
35        }
36      
37        // Initialize the previous maximum value for use in calculating gaps
38        int prevMax = Integer.MAX_VALUE;
39        // Initialize answer for the maximum gap
40        int answer = 0;
41      
42        // Iterate through the buckets to find the maximum gap between successive buckets
43        for (int[] bucket : buckets) {
44            // Ignore empty buckets
45            if (bucket[0] > bucket[1]) {
46                continue;
47            }
48            // Calculate the gap between current bucket's minimum and previous bucket's maximum
49            answer = Math.max(answer, bucket[0] - prevMax);
50            // Update previous maximum to the current bucket's maximum
51            prevMax = bucket[1];
52        }
53      
54        // Return the maximum gap found
55        return answer;
56    }
57}
58

1#include <vector>
2#include <algorithm>
3#include <climits>
4using namespace std;
5
6class Solution {
7public:
8    // Function to calculate the maximum gap between consecutive elements after sorting
9    int maximumGap(vector<int>& nums) {
10        int n = nums.size(); // Store the size of the input vector
11      
12        // If there are less than two elements, no gap exists
13        if (n < 2) return 0;
14      
15        // Initialize variables to store the minimum and maximum values in the list
16        int minValue = INT_MAX, maxValue = INT_MIN;
17      
18        // Determine the minimum and maximum values in the input list
19        for (int value : nums) {
20            minValue = min(minValue, value);
21            maxValue = max(maxValue, value);
22        }
23      
24        // Calculate bucket size with a minimum of 1 to avoid division by zero
25        int bucketSize = max(1, (maxValue - minValue) / (n - 1));
26      
27        // Calculate the number of buckets required
28        int bucketCount = (maxValue - minValue) / bucketSize + 1;
29      
30        // Pair to store the minimum and maximum within a bucket
31        using Pii = pair<int, int>;
32      
33        // Create a vector of pairs to represent buckets, initialized with extreme values
34        vector<Pii> buckets(bucketCount, {INT_MAX, INT_MIN});
35      
36        // Place each number in its corresponding bucket
37        for (int value : nums) {
38            int bucketIndex = (value - minValue) / bucketSize;
39            buckets[bucketIndex].first = min(buckets[bucketIndex].first, value); // Update bucket min
40            buckets[bucketIndex].second = max(buckets[bucketIndex].second, value); // Update bucket max
41        }
42      
43        // Initialize the variable to store the maximum gap
44        int maxGap = 0;
45      
46        // Variable to store the maximum of the previous encountered bucket
47        int previousMax = INT_MAX;
48      
49        // Iterate through the buckets to find the maximum gap
50        for (const Pii& bucket : buckets) {
51            // Skip empty buckets
52            if (bucket.first > bucket.second) continue;
53          
54            // Update the maximum gap if the current gap is larger
55            maxGap = max(maxGap, bucket.first - previousMax);
56          
57            // Update the previous maximum for the next iteration
58            previousMax = bucket.second;
59        }
60      
61        // Return the maximum gap after traversing through the buckets
62        return maxGap;
63    }
64};
65

1// Import statements are not necessary in TypeScript for this context
2
3// Function interface for the pair of minimum and maximum values
4interface MinMaxPair {
5    min: number;
6    max: number;
7}
8
9// Function to calculate the maximum gap between consecutive elements after sorting
10function maximumGap(nums: number[]): number {
11    const n: number = nums.length; // Store the size of the input array
12  
13    // If there are fewer than two elements, no gap exists
14    if (n < 2) return 0;
15  
16    // Initialize variables to store the minimum and maximum values in the list
17    let minValue: number = Number.MAX_SAFE_INTEGER;
18    let maxValue: number = Number.MIN_SAFE_INTEGER;
19  
20    // Determine the minimum and maximum values in the input list
21    nums.forEach((value: number) => {
22        minValue = Math.min(minValue, value);
23        maxValue = Math.max(maxValue, value);
24    });
25
26    // Calculate bucket size with a minimum of 1 to avoid division by zero
27    const bucketSize: number = Math.max(1, Math.floor((maxValue - minValue) / (n - 1)));
28  
29    // Calculate the number of buckets required
30    const bucketCount: number = Math.floor((maxValue - minValue) / bucketSize) + 1;
31  
32    // Create an array of pairs to represent buckets, initialized with extreme values
33    const buckets: MinMaxPair[] = new Array(bucketCount).fill(null).map(() => ({
34        min: Number.MAX_SAFE_INTEGER,
35        max: Number.MIN_SAFE_INTEGER
36    }));
37
38    // Place each number in its corresponding bucket
39    nums.forEach((value: number) => {
40        const bucketIndex: number = Math.floor((value - minValue) / bucketSize);
41        buckets[bucketIndex].min = Math.min(buckets[bucketIndex].min, value); // Update bucket min
42        buckets[bucketIndex].max = Math.max(buckets[bucketIndex].max, value); // Update bucket max
43    });
44  
45    // Initialize the variable to store the maximum gap
46    let maxGap: number = 0;
47
48    // Variable to store the maximum of the previous encountered bucket
49    let previousMax: number = minValue; // Initialize to the minimum value
50
51    // Iterate through the buckets to find the maximum gap
52    buckets.forEach((bucket: MinMaxPair) => {
53        // Skip empty buckets
54        if (bucket.min > bucket.max) return;
55      
56        // Update the maximum gap if the current gap is larger
57        maxGap = Math.max(maxGap, bucket.min - previousMax);
58      
59        // Update the previous maximum for the next iteration
60        previousMax = bucket.max;
61    });
62  
63    // Return the maximum gap after traversing through the buckets
64    return maxGap;
65}
66

Time and Space Complexity

Time Complexity

The time complexity of the code can be broken down into the following parts:

Finding the minimum (mi) and maximum (mx) elements in the list nums, which takes O(n) time.
Calculating the bucket_size and bucket_count, which is done in constant time, hence O(1).
Initializing the buckets list, which takes O(bucket_count). Since bucket_count is ideally O(n), this initialization is O(n).
Populating the buckets with minimum and maximum values for each bucket. Each element in the list nums is visited once, hence this is O(n).
Finally, iterating through all the buckets to find the maximum gap, which is at most O(n) because there are bucket_count buckets, and bucket_count is ideally less than or equal to n.

Combining all these, the overall time complexity is O(n) because the other operations contribute a constant or lower order addition to the complexity which doesn't change the overall order of n.

Space Complexity

The space complexity of the code can be analyzed by looking at the additional space required:

Space for the buckets, which would be O(bucket_count). Since bucket_count is ideally O(n), this contributes O(n) space complexity.
Constant space for storing variables like mi, mx, bucket_size, ans, and prev, which is O(1).

Therefore, the total space complexity of the algorithm is O(n) for the buckets, with additional constant space for the variables. Thus, the overall space complexity is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

dp[i] = dp[i - 1] + dp[i - 2]

dp[i] = dp[i - 1] + 1

dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

dp[i] = dp[i - 1]

I don't know