Maximum Gap (Bucket Sort)

# Maximum Gap (Bucket Sort) ## Difficulty Hard ## Tags `array`, `bucket sort`, `sorting` ## Problem Statement Given an integer array `nums`, return the maximum difference between two successive elements in its sorted form. If the array contains fewer than 2 elements, return 0. **Challenge**: Solve it in linear time O(N) and linear space O(N). ## Constraints - 1 ≤ nums.length ≤ 10⁵ - 0 ≤ nums[i] ≤ 10⁹ ## Signatures ### Python ```python def maximum_gap(nums: List[int]) -> int: pass ``` ### Java ```java public class Solution { public int maximum_gap(List<Integer> nums) { return null; } } ``` ### Csharp ```csharp public class Solution { public int maximum_gap(IList<int> nums) { throw new NotImplementedException(); } } ``` ### Cpp ```cpp class Solution { public: int maximum_gap(vector<int> nums) { } }; ``` ### C ```c int maximum_gap(int* nums) { } ``` ### Ruby ```ruby def maximum_gap(nums) end ``` ### Perl ```perl sub maximum_gap { my ($self, @args) = @_; } ``` ### Scala ```scala object Solution { def maximum_gap(nums: List[Int]): Int = { } } ``` ### Haskell ```haskell maximum_gap :: ... -> ... maximum_gap args = undefined ``` ### Clojure ```clojure (defn maximum_gap [nums] ) ``` ### Scheme ```scheme (define (maximum_gap nums) ) ``` ## Examples ### Example 1 **Input:** ``` nums = [3, 6, 9, 1] ``` **Output:** ``` 3 ``` **Explanation:** Sorted: [1, 3, 6, 9]. Gaps: 2, 3, 3. Maximum is 3. ### Example 2 **Input:** ``` nums = [10] ``` **Output:** ``` 0 ``` ### Example 3 **Input:** ``` nums = [1, 10000000] ``` **Output:** ``` 9999999 ``` ## Hints ### Why Bucket Sort? - Standard comparison sorts are O(N log N). - We can achieve O(N) using the Pigeonhole Principle. ### Algorithm 1. Find min and max values in the array. 2. Calculate bucket size: `gap = ceil((max - min) / (n - 1))`. 3. Create n-1 buckets. Each bucket tracks its local min and max. 4. Place each element in appropriate bucket: `bucket_idx = (num - min) / gap`. 5. The maximum gap must be between buckets (not within a bucket). 6. Iterate through buckets, tracking max of previous bucket's max vs current bucket's min. ### Key Insight If we have n elements in range [min, max], the average gap is `(max - min) / (n - 1)`. The maximum gap must be at least this average, so it cannot be within a single bucket of this size.