164. Maximum Gap
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 returns0
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 ofnums
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 least1
. 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
asinf
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 thecurmin
of the current bucket and theprev
(which is thecurmax
of the previous non-empty bucket). We updateans
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 EvaluatorExample 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
is1
and the maximum valuemx
is9
. -
Bucket Size and Count: With
n = 5
elements, the bucket size is calculated as a maximum of1
and(9 - 1) // (5 - 1)
which is2
. There will be⌈(9 - 1) / 2⌉ = 4
buckets to cover the range from1
to9
. -
Bucket Initialization: We create 4 buckets, each initialized to have a minimum (curmin) of
infinity
and a maximum (curmax) of-infinity
:1Buckets: [[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 bucket1
((3 - 1) // 2
), updating curmin and curmax to3
.6
goes into bucket2
((6 - 1) // 2
), updating curmin and curmax to6
.9
goes into bucket4
((9 - 1) // 2
), since this is the last bucket, it simply updates curmin and curmax to9
.1
goes into bucket0
((1 - 1) // 2
), updating curmin and curmax to1
.4
goes into bucket1
((4 - 1) // 2
), updating curmin to3
if necessary and curmax to4
.
The buckets now look like:
1Buckets: [[1, 1], [3, 4], [6, 6], [inf, -inf], [9, 9]]
-
Finding the Maximum Gap: We set
prev
to1
(the maximum of the first bucket, bucket0
). Then, we calculate the gaps:- The gap between buckets
0
and1
is3 - 1 = 2
. - The gap between buckets
1
and2
is6 - 4 = 2
. - Bucket
3
is empty (stillinf, -inf
), so we skip it. - The gap between buckets
2
and4
is9 - 6 = 3
.
Therefore, the maximum gap we've found is
3
. - The gap between buckets
-
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 listnums
, which takesO(n)
time. - Calculating the
bucket_size
andbucket_count
, which is done in constant time, henceO(1)
. - Initializing the
buckets
list, which takesO(bucket_count)
. Sincebucket_count
is ideallyO(n)
, this initialization isO(n)
. - Populating the
buckets
with minimum and maximum values for each bucket. Each element in the listnums
is visited once, hence this isO(n)
. - Finally, iterating through all the
buckets
to find the maximum gap, which is at mostO(n)
because there arebucket_count
buckets, andbucket_count
is ideally less than or equal ton
.
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 beO(bucket_count)
. Sincebucket_count
is ideallyO(n)
, this contributesO(n)
space complexity. - Constant space for storing variables like
mi
,mx
,bucket_size
,ans
, andprev
, which isO(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.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.