Maximum Gap
MedPrompt
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 <= 1050 <= nums[i] <= 109
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward approach is to sort the array first and then find the maximum difference between adjacent elements. This guarantees that we are comparing successive elements as required by the problem, as the maximum gap in the sorted version of the array must lie between two consecutive elements.
Algorithm
- If the length of the input array
numsis less than 2, return 0. - Sort the array
numsin ascending order. Most standard library sort functions have a time complexity of O(N log N). - Initialize a variable
maxGapto 0. - Iterate through the sorted array from the second element (index 1) to the end.
- In each iteration, calculate the difference between the current element and its predecessor (
nums[i] - nums[i-1]). - Update
maxGapto be the maximum of its current value and the calculated difference. - After iterating through the entire array, return
maxGap.
Walkthrough
This method leverages standard sorting algorithms. The core idea is that once the array is sorted, the two elements that form the maximum gap must be adjacent in the sorted sequence.
import java.util.Arrays; class Solution { public int maximumGap(int[] nums) { if (nums == null || nums.length < 2) { return 0; } Arrays.sort(nums); int maxGap = 0; for (int i = 1; i < nums.length; i++) { maxGap = Math.max(maxGap, nums[i] - nums[i-1]); } return maxGap; }}Complexity
Time
O(N log N)
Space
O(log N) to O(N)
Trade-offs
Pros
Very simple to understand and implement.
Leverages built-in, highly-optimized sorting functions.
Cons
The time complexity of O(N log N) does not meet the problem's requirement of a linear time algorithm.
To meet the linear time requirement, we can replace the comparison-based sort with a linear-time sorting algorithm. Since the input consists of non-negative integers, Radix Sort is an excellent choice. It sorts the array in O(N) time, after which we can find the maximum gap in a single pass.
Algorithm
- If the array has fewer than two elements, return 0.
- Sort the array
numsusing Radix Sort. Radix sort processes numbers digit by digit (or by groups of bits) and uses a stable sorting subroutine like Counting Sort. - For numbers up to 10^9, we can sort based on decimal digits or, more efficiently, by bytes.
- Once the array is sorted in linear time, initialize
maxGapto 0. - Perform a single pass through the sorted array from the second element.
- Calculate the difference
nums[i] - nums[i-1]and updatemaxGapwith the maximum difference found. - Return
maxGap.
Walkthrough
Radix sort works by sorting numbers based on their individual digits, starting from the least significant digit and moving to the most significant. For each digit, it uses a stable sort (like counting sort) to arrange the numbers. Because the range of values for each digit (0-9) is small and the number of digits is constant for the given constraints (up to 10^9), the overall time complexity is linear.
import java.util.Arrays; class Solution { // Radix sort helper private void radixSort(int[] nums) { if (nums.length < 2) return; int maxVal = 0; for (int num : nums) { maxVal = Math.max(maxVal, num); } long exp = 1; int[] buffer = new int[nums.length]; while (maxVal / exp > 0) { int[] count = new int[10]; for (int num : nums) { count[(int)((num / exp) % 10)]++; } for (int i = 1; i < 10; i++) { count[i] += count[i - 1]; } for (int i = nums.length - 1; i >= 0; i--) { buffer[--count[(int)((nums[i] / exp) % 10)]] = nums[i]; } System.arraycopy(buffer, 0, nums, 0, nums.length); exp *= 10; } } public int maximumGap(int[] nums) { if (nums == null || nums.length < 2) { return 0; } radixSort(nums); int maxGap = 0; for (int i = 1; i < nums.length; i++) { maxGap = Math.max(maxGap, nums[i] - nums[i-1]); } return maxGap; }}Complexity
Time
O(N)
Space
O(N)
Trade-offs
Pros
Achieves the required O(N) time complexity.
Satisfies the problem constraints.
Cons
Implementation is more complex than comparison sorting.
Can have a larger constant factor in its time complexity compared to the more specialized bucket sort approach.
The most optimal approach uses principles from Bucket Sort and the Pigeonhole Principle. It solves the problem in linear time and space without fully sorting the array. The key insight is that if we distribute the numbers into buckets of a certain size, the maximum gap cannot occur between two numbers that fall into the same bucket. Therefore, we only need to compare the boundaries of adjacent non-empty buckets.
Algorithm
- Handle the edge case: if the array has fewer than 2 elements, return 0.
- Find the minimum (
minVal) and maximum (maxVal) elements in the array in one pass. - If
minVal == maxVal, all elements are identical, so return 0. - Calculate an appropriate bucket size. A good choice is
bucketSize = max(1, (maxVal - minVal) / (N - 1)). This ensures the maximum gap is at leastbucketSize. - Calculate the number of buckets needed:
bucketCount = (maxVal - minVal) / bucketSize + 1. - Create two arrays,
bucketMinandbucketMax, of sizebucketCountto store the minimum and maximum values for each bucket. Initialize them with sentinel values. - Iterate through the input numbers. For each number
num, calculate its bucket indexidx = (num - minVal) / bucketSizeand update the min/max values inbucketMin[idx]andbucketMax[idx]. - Initialize
maxGap = 0andpreviousMax = minVal. - Iterate through the buckets. For each non-empty bucket, calculate the gap between its minimum value and the maximum value of the previous non-empty bucket (
bucketMin[i] - previousMax). UpdatemaxGapwith this value. - Update
previousMaxto the current bucket's maximum value. - Return
maxGap.
Walkthrough
This algorithm cleverly avoids a full sort. By creating buckets of size b = (max - min) / (N - 1), we know the maximum gap must be at least b. Any two numbers within the same bucket can have a gap of at most b-1. Thus, the maximum gap can only be found by comparing the maximum value of a bucket with the minimum value of the next non-empty bucket. This reduces the number of comparisons from O(N) (in a sorted array) to O(num_buckets), which is also O(N).
import java.util.Arrays; class Solution { public int maximumGap(int[] nums) { if (nums == null || nums.length < 2) { return 0; } int n = nums.length; int minVal = nums[0]; int maxVal = nums[0]; for (int num : nums) { minVal = Math.min(minVal, num); maxVal = Math.max(maxVal, num); } if (maxVal == minVal) { return 0; } int bucketSize = Math.max(1, (maxVal - minVal) / (n - 1)); int bucketCount = (maxVal - minVal) / bucketSize + 1; int[] bucketMin = new int[bucketCount]; int[] bucketMax = new int[bucketCount]; Arrays.fill(bucketMin, Integer.MAX_VALUE); Arrays.fill(bucketMax, Integer.MIN_VALUE); for (int num : nums) { int bucketIdx = (num - minVal) / bucketSize; bucketMin[bucketIdx] = Math.min(bucketMin[bucketIdx], num); bucketMax[bucketIdx] = Math.max(bucketMax[bucketIdx], num); } int maxGap = 0; int previousMax = minVal; for (int i = 0; i < bucketCount; i++) { if (bucketMin[i] == Integer.MAX_VALUE) { // Empty bucket continue; } maxGap = Math.max(maxGap, bucketMin[i] - previousMax); previousMax = bucketMax[i]; } return maxGap; }}Complexity
Time
O(N)
Space
O(N)
Trade-offs
Pros
Achieves optimal O(N) time and O(N) space complexity.
Highly efficient as it avoids a full sort and only requires a few passes over the data.
Cons
The logic is more complex and less intuitive than a simple sort.
Requires careful calculation of bucket size and handling of edge cases to work correctly.
Solutions
Solution
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 ; } }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 ; } }''' >>> 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// 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 ); } };Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.