Problem Description

Given an integer array nums, you need to find the maximum difference between two successive elements after the array is sorted. If the array contains less than two elements, return 0.

The challenge is to solve this problem in linear time complexity O(n) and using linear extra space O(n).

For example:

• If nums = [3, 6, 9, 1], after sorting it becomes [1, 3, 6, 9]. The successive differences are 3-1=2, 6-3=3, and 9-6=3. The maximum gap is 3.
• If nums = [10], there's only one element, so return 0.

The key insight is using bucket sort principles. Since we need linear time complexity, we cannot use comparison-based sorting algorithms like quicksort or mergesort which have O(n log n) complexity.

The algorithm works by:

1. Finding the minimum and maximum values in the array
2. Creating buckets with calculated bucket size based on the range (max - min) / (n - 1)
3. Distributing elements into buckets and tracking the min and max values in each bucket
4. The maximum gap must occur between the maximum element of one bucket and the minimum element of the next non-empty bucket (not within the same bucket due to the pigeonhole principle)
5. Iterating through buckets to find the maximum gap between successive non-empty buckets

This approach ensures that the maximum gap is found efficiently without explicitly sorting the entire array.

Intuition

When we need to find the maximum gap between successive elements in a sorted array in linear time, we can't use traditional sorting algorithms since they take O(n log n) time. This constraint pushes us to think about non-comparison based sorting approaches.

The key observation is that if we have n numbers and we know the minimum and maximum values, we can estimate what the minimum possible maximum gap would be. This minimum possible gap occurs when all numbers are evenly distributed, which would be (max - min) / (n - 1).

Why is this important? Because the actual maximum gap must be at least this value or larger. This gives us a clever idea: if we create buckets of size (max - min) / (n - 1), then by the pigeonhole principle, at least one bucket must be empty (unless all numbers are evenly distributed).

Here's the crucial insight: since each bucket has a size equal to the minimum possible maximum gap, the maximum gap cannot occur between two numbers within the same bucket. It must occur between numbers in different buckets - specifically between the maximum value of one bucket and the minimum value of the next non-empty bucket.

This transforms our problem from "sort all elements and find the maximum gap" to "distribute elements into buckets, track min/max of each bucket, and find the maximum gap between consecutive non-empty buckets". We only need to track the minimum and maximum values in each bucket, not all the elements, which keeps our space complexity linear.

The bucket approach works because:

1. Elements in the same bucket are close to each other (within the bucket size range)
2. The gap between buckets is guaranteed to be at least the bucket size
3. We can process all elements in one pass to fill buckets (O(n))
4. We can scan through buckets once to find the maximum gap (O(n))

Solution Approach

Let's walk through the implementation step by step:

1. Handle edge case: If the array has less than 2 elements, return 0 immediately since there's no gap to calculate.

2. Find the range: Calculate the minimum (mi) and maximum (mx) values in the array. This helps us determine the range of values we're working with.

3. Calculate bucket size: The bucket size is computed as max(1, (mx - mi) // (n - 1)). We use max(1, ...) to ensure the bucket size is at least 1 to avoid division by zero when all elements are the same.

4. Determine bucket count: The number of buckets needed is (mx - mi) // bucket_size + 1. This ensures we have enough buckets to cover the entire range.

5. Initialize buckets: Create bucket_count buckets, where each bucket is represented as [min_value, max_value]. Initially, set them to [inf, -inf] to indicate empty buckets.

6. Distribute elements into buckets: For each number v in the array:

   • Calculate which bucket it belongs to: i = (v - mi) // bucket_size
   • Update the bucket's minimum value: buckets[i][0] = min(buckets[i][0], v)
   • Update the bucket's maximum value: buckets[i][1] = max(buckets[i][1], v)

7. Find maximum gap:

   • Initialize ans = 0 to track the maximum gap
   • Initialize prev = inf to track the maximum value of the previous non-empty bucket
   • Iterate through all buckets:
     • Skip empty buckets (where curmin > curmax)
     • Calculate the gap between current bucket's minimum and previous bucket's maximum: curmin - prev
     • Update the maximum gap: ans = max(ans, curmin - prev)
     • Update prev to current bucket's maximum for the next iteration

8. Return result: The variable ans now contains the maximum gap between successive elements.

The algorithm achieves O(n) time complexity through single-pass operations: finding min/max (O(n)), distributing elements (O(n)), and scanning buckets (O(n)). The space complexity is also O(n) for storing the buckets.

Example Walkthrough

Let's walk through the algorithm with nums = [3, 6, 9, 1]:

Step 1: Find min and max

• min = 1, max = 9
• Range = 9 - 1 = 8

Step 2: Calculate bucket size

• We have n = 4 elements
• Bucket size = (max - min) / (n - 1) = 8 / 3 = 2.67, rounded down to 2
• This means each bucket covers a range of 2 units

Step 3: Create buckets

• Number of buckets = (9 - 1) / 2 + 1 = 5 buckets
• Initialize 5 buckets: [[inf, -inf], [inf, -inf], [inf, -inf], [inf, -inf], [inf, -inf]]

Step 4: Distribute elements into buckets

• Element 3: bucket index = (3 - 1) / 2 = 1 → Bucket 1: [3, 3]
• Element 6: bucket index = (6 - 1) / 2 = 2 → Bucket 2: [6, 6]
• Element 9: bucket index = (9 - 1) / 2 = 4 → Bucket 4: [9, 9]
• Element 1: bucket index = (1 - 1) / 2 = 0 → Bucket 0: [1, 1]

Buckets after distribution:

• Bucket 0: [1, 1] (contains value 1)
• Bucket 1: [3, 3] (contains value 3)
• Bucket 2: [6, 6] (contains value 6)
• Bucket 3: [inf, -inf] (empty)
• Bucket 4: [9, 9] (contains value 9)

Step 5: Find maximum gap between consecutive non-empty buckets

• Start with prev = inf, max_gap = 0
• Bucket 0 [1, 1]: First non-empty bucket, set prev = 1
• Bucket 1 [3, 3]: Gap = 3 - 1 = 2, update max_gap = 2, set prev = 3
• Bucket 2 [6, 6]: Gap = 6 - 3 = 3, update max_gap = 3, set prev = 6
• Bucket 3: Empty, skip
• Bucket 4 [9, 9]: Gap = 9 - 6 = 3, max_gap remains 3

Result: The maximum gap is 3, which matches the expected result when sorting [1, 3, 6, 9] and finding the largest difference between consecutive elements.

Notice how Bucket 3 is empty, demonstrating that the maximum gap (3) indeed occurs between buckets (from Bucket 2's max to Bucket 4's min), not within any single bucket. This validates our bucket size calculation and the pigeonhole principle at work.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the input array nums. This is because:

• Finding the minimum and maximum values takes O(n) time
• Creating the buckets array takes O(bucket_count) time, where bucket_count ≤ n
• Distributing all elements into buckets requires one pass through the array, taking O(n) time
• The final loop through buckets takes O(bucket_count) time, which is at most O(n)

The space complexity is O(n). This is because:

• The buckets array has size bucket_count, which is calculated as (mx - mi) // bucket_size + 1
• Since bucket_size = max(1, (mx - mi) // (n - 1)), the bucket_count is approximately n in the worst case
• Each bucket stores exactly 2 values (min and max), so the total space used is O(bucket_count) = O(n)

Common Pitfalls

Pitfall 1: Incorrect Bucket Size Calculation

Problem: When all elements in the array are identical (e.g., nums = [1, 1, 1, 1]), the calculation (max_val - min_val) // (n - 1) results in 0 // 3 = 0, which would cause division by zero errors when determining bucket indices.

Solution: Always ensure the bucket size is at least 1 by using max(1, (max_val - min_val) // (n - 1)). This handles the edge case where all elements are the same, resulting in a maximum gap of 0.

Pitfall 2: Off-by-One Error in Bucket Count

Problem: Calculating bucket count as simply (max_val - min_val) // bucket_size can miss the last bucket. For example, if the range is 10 and bucket_size is 3, we'd get 3 buckets, but we actually need 4 to cover values at positions 0-2, 3-5, 6-8, and 9-10.

Solution: Add 1 to the bucket count calculation: (max_val - min_val) // bucket_size + 1. This ensures all values in the range are covered.

Pitfall 3: Incorrect Gap Calculation Between Buckets

Problem: A common mistake is calculating the gap as current_max - prev_max or current_min - prev_min, which doesn't give the actual gap between successive elements.

Solution: The correct gap between successive elements is current_min - prev_max. The gap occurs between the maximum of one bucket and the minimum of the next non-empty bucket.

Pitfall 4: Not Initializing prev_max Correctly

Problem: Initializing prev_max to 0 or the minimum value can lead to incorrect gap calculations for the first non-empty bucket.

Solution: Initialize prev_max to inf initially, then in the loop, only calculate the gap after encountering the first non-empty bucket. The code handles this by checking max_gap = max(max_gap, current_min - prev_max) where the first calculation with inf will be negative and won't affect the result.

Pitfall 5: Forgetting the Pigeonhole Principle

Problem: Attempting to find the maximum gap within buckets rather than between buckets, which defeats the purpose of the bucket sort optimization.

Solution: Remember that by the pigeonhole principle, when we have n-1 gaps and create buckets of size (max-min)/(n-1), the maximum gap cannot occur within a single bucket—it must occur between buckets. This is why we only track min and max for each bucket rather than all elements.