Maximum Gap

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: 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.

Consider these constraints:

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^9

## Maximum Gap Problem

This problem asks us to find the maximum difference between two successive elements in the sorted form of an integer array.  The solution must run in linear time and use linear extra space.

### 1. Naive Solution (Sorting)

The simplest approach is to sort the array and then iterate through the sorted array to find the maximum difference between adjacent elements.

```python
def maximum_gap_naive(nums):
    if len(nums) < 2:
        return 0
    nums.sort()
    max_diff = 0
    for i in range(1, len(nums)):
        max_diff = max(max_diff, nums[i] - nums[i-1])
    return max_diff

2. Optimal Solution (Bucket Sort / Pigeonhole Principle)

To achieve linear time complexity, we can use a bucket sort-like approach leveraging the Pigeonhole Principle. The idea is:

1. Find Min and Max: Determine the minimum and maximum values in the array.
2. Calculate Bucket Size: Divide the range (max - min) into n - 1 buckets. The size of each bucket will be (max - min) / (n - 1). This ensures that at least one bucket will be empty, guaranteeing that the maximum gap will be at least as large as the bucket size.
3. Assign to Buckets: Distribute each number into its corresponding bucket, keeping track of the minimum and maximum values within each bucket.
4. Find Maximum Gap: Iterate through the buckets. The maximum gap will be the largest difference between the maximum value of one bucket and the minimum value of the next non-empty bucket.

def maximum_gap(nums):
    n = len(nums)
    if n < 2:
        return 0

    min_val = min(nums)
    max_val = max(nums)

    if min_val == max_val:
        return 0

    bucket_size = (max_val - min_val) / (n - 1)
    if bucket_size == 0:
        bucket_size = 1  # Avoid division by zero if all elements are the same

    bucket_count = n - 1
    min_buckets = [float('inf')] * bucket_count
    max_buckets = [float('-inf')] * bucket_count

    for num in nums:
        bucket_index = int((num - min_val) / bucket_size)
        if bucket_index >= bucket_count:
           bucket_index = bucket_count -1
        min_buckets[bucket_index] = min(min_buckets[bucket_index], num)
        max_buckets[bucket_index] = max(max_buckets[bucket_index], num)

    max_gap = 0
    previous_max = min_val
    for i in range(bucket_count):
        if min_buckets[i] == float('inf'):
            continue  # Skip empty buckets
        max_gap = max(max_gap, min_buckets[i] - previous_max)
        previous_max = max_buckets[i]

    max_gap = max(max_gap, max_val - previous_max)

    return max_gap

3. Big(O) Run-time Analysis

• Naive Solution: Sorting the array takes O(n log n) time. Iterating through the sorted array takes O(n) time. Therefore, the overall time complexity is O(n log n).
• Optimal Solution: Finding the min and max takes O(n) time. Assigning numbers to buckets takes O(n) time. Iterating through the buckets takes O(n) time. Therefore, the overall time complexity is O(n).

4. Big(O) Space Usage Analysis

• Naive Solution: Sorting may take O(log n) space depending on the sorting algorithm used (e.g., merge sort). Therefore, the overall space complexity is O(log n) in many implementations, and O(n) in others. In place sorts have O(1) space complexity.
• Optimal Solution: We use min_buckets and max_buckets, each of size n - 1. Therefore, the space complexity is O(n).

5. Edge Cases and Handling

• Empty Array or Single Element: If the array has fewer than two elements, the maximum difference is 0. This is handled at the beginning of both the naive and optimal solutions.
• All Elements are the Same: If all elements are the same, the min and max will be equal. The bucket size calculation should handle cases to prevent division by zero, and ensure correct behavior. Also, we must handle this case in both solutions since if min_val == max_val, then we simply return 0.
• Large Range of Values: The bucket size calculation could potentially result in floating-point inaccuracies. In this case the bucket index should be cast to an integer. Also, if we use a really really large range, we could run into memory issues since we need to allocate for all n-1 buckets.
• Negative Numbers: The solution works correctly with negative numbers since we find the min/max range and distribute buckets based on relative position to the min/max values.