Watch 10 video solutions for Maximum Gap, a medium level problem involving Array, Sorting, Bucket Sort. This walkthrough by NeetCode has 665,789 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 109Problem Overview: You are given an unsorted integer array. After sorting the array, compute the maximum difference between two consecutive elements. The challenge is solving it efficiently for large inputs where a full comparison-based sort may not be optimal.
Approach 1: Sorting the Array (O(n log n) time, O(1)–O(n) space)
The straightforward approach is to sort the array using a standard sorting algorithm and then scan the sorted result to find the largest gap between adjacent elements. First call the language's built-in sort. Then iterate from index 1 to n-1 and compute nums[i] - nums[i-1], tracking the maximum difference.
This works because once the array is sorted, the maximum adjacent gap must appear between two neighboring values in that order. The implementation is short and reliable since optimized library sorts are highly tuned. Time complexity is O(n log n), and space complexity ranges from O(1) to O(n) depending on the sorting implementation.
This approach is usually acceptable in practice and is easy to explain during interviews. However, the problem specifically encourages a linear-time idea using non-comparison sorting.
Approach 2: Bucket Sort / Pigeonhole Principle (O(n) time, O(n) space)
The optimal solution uses the pigeonhole principle and a variation of bucket sort. Instead of fully sorting the array, compute the global minimum and maximum values first. If there are n numbers, the minimum possible maximum gap must be at least (max - min) / (n - 1). This value determines the bucket size.
Create buckets that each store only two values: the minimum and maximum number placed in that bucket. Iterate through the array and place each value into its bucket using an index like (num - min) / bucketSize. You never store every element inside the bucket—only the local min and max.
The key insight: the maximum gap cannot occur inside a bucket because bucket width is bounded. The real gap appears between the maximum of one bucket and the minimum of the next non-empty bucket. After filling buckets, iterate through them, skipping empty ones, and compute the difference between consecutive bucket boundaries.
This reduces the problem to linear passes over the array and bucket list. Time complexity becomes O(n) with O(n) space. The idea is closely related to distribution-based methods like radix sort and is commonly used when the value range can guide partitioning.
Recommended for interviews: Start with the sorting solution because it clearly demonstrates correctness and problem understanding. Then move to the bucket-based linear solution. Interviewers typically expect candidates to recognize the pigeonhole principle and explain why the maximum gap must occur between buckets rather than inside them.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting the Array | O(n log n) | O(1)–O(n) | Simple implementation using built-in sort. Good when constraints are moderate. |
| Bucket Sort (Pigeonhole Principle) | O(n) | O(n) | Optimal solution when linear time is required and value range can define buckets. |