LeetCode 164: Maximum Gap Solution in Python Explained

Problem Statement

In LeetCode 164, you’re given an integer array nums. Your task is to return the maximum gap between any two successive elements in its sorted form, achieving O(n) time complexity and O(1) extra space (excluding input/output). If the array has fewer than 2 elements, return 0. This differs from range finding like LeetCode 163: Missing Ranges, focusing on maximum differences rather than missing intervals.

Constraints

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

Example

Let’s see some cases:

Input: nums = [3,6,9,1]
Output: 3
Explanation: Sorted: [1,3,6,9], gaps: 2, 3, 3, max gap = 3.

Input: nums = [10]
Output: 0
Explanation: Fewer than 2 elements, return 0.

Input: nums = [1,5,10,14,15]
Output: 5
Explanation: Sorted: [1,5,10,14,15], gaps: 4, 5, 4, 1, max gap = 5.

These examples show we’re finding the largest successive difference.

Understanding the Problem

How do you solve LeetCode 164: Maximum Gap in Python? Take nums = [3,6,9,1]. Sorted, it’s [1,3,6,9], with gaps 2 (3-1), 3 (6-3), 3 (9-6), so the maximum is 3. For [1,5,10,14,15], gaps are 4, 5, 4, 1, max is 5. The O(n) time constraint rules out standard O(n log n) sorting, suggesting a linear-time approach like bucket sort. This isn’t a peak-finding task like LeetCode 162: Find Peak Element; it’s about maximum sorted differences. We’ll use: 1. Bucket Sort: O(n) time, O(n) space—our best solution. 2. Sorting with Linear Scan: O(n log n) time, O(1) space—an alternative.

Let’s dive into the best solution.

Best Solution: Bucket Sort Approach

Explanation

Bucket Sort distributes numbers into buckets to find the maximum gap without fully sorting:

• Find min and max values, compute bucket size as (max - min) / (n - 1).
• Create buckets, each tracking min and max values within its range.
• Place numbers into buckets, updating their min/max.
• Scan buckets for the max gap between consecutive non-empty buckets.

This achieves O(n) time (n = array length) by avoiding full sorting, using O(n) space for buckets, which is optimal given the constraint interpretation.

For [3,6,9,1]:

• Min=1, Max=9, bucket size=2.66, 3 buckets.
• Buckets: [1-3], [4-6], [7-9] → [1], [6], [9].
• Gaps: 6-1=5, 9-6=3, max=5 (actual max=3, but bucket gap approximates).

Step-by-Step Example

Example 1: nums = [3,6,9,1]

Goal: Return 3.

• Step 1: n=4, min_val=1, max_val=9.
• Step 2: bucket_size = (9-1)/(4-1) = 2.66 ≈ 2, num_buckets = 3.
• Step 3: Buckets: [0:1-3], [1:4-6], [2:7-9].
• bucket_min = [1,inf,inf], bucket_max = [-inf,6,9].
• 3→bucket 0, 6→bucket 1, 9→bucket 2, 1→bucket 0.
• Update: bucket_min = [1,6,inf], bucket_max = [3,6,9].
• Step 4: Gaps:
• 6-3=3, 9-6=3, max=3.
• Finish: Return 3.

Example 2: nums = [10]

Goal: Return 0.

• Step 1: n=1, fewer than 2, return 0.
• Finish: Return 0.

Example 3: nums = [1,5,10,14,15]

Goal: Return 5.

• Step 1: n=5, min_val=1, max_val=15.
• Step 2: bucket_size = (15-1)/(5-1) = 3.5 ≈ 3, num_buckets = 5.
• Step 3: Buckets: [0:1-4], [1:5-8], [2:9-12], [3:13-16], [4:17-20].
• bucket_min = [1,5,10,14,inf], bucket_max = [1,5,10,15,-inf].
• Step 4: Gaps: 5-1=4, 10-5=5, 14-10=4, 15-14=1, max=5.
• Finish: Return 5.

How the Code Works (Bucket Sort) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

def maximumGap(nums: list[int]) -> int:
    # Line 1: Handle base cases
    if len(nums) < 2:
        # Fewer than 2 elements (e.g., [10])
        return 0

    # Line 2: Find min and max
    n = len(nums)
    min_val = min(nums)
    # Minimum value (e.g., 1)
    max_val = max(nums)
    # Maximum value (e.g., 9)

    # Line 3: Calculate bucket size and count
    bucket_size = max(1, (max_val - min_val) // (n - 1))
    # Ensure at least 1 (e.g., (9-1)//(4-1)=2)
    num_buckets = (max_val - min_val) // bucket_size + 1
    # Number of buckets (e.g., 8//2+1=5)

    # Line 4: Initialize buckets
    bucket_min = [float('inf')] * num_buckets
    # Min values per bucket (e.g., [inf]*3)
    bucket_max = [float('-inf')] * num_buckets
    # Max values per bucket (e.g., [-inf]*3)

    # Line 5: Fill buckets
    for num in nums:
        # Process each number (e.g., 3,6,9,1)
        bucket_idx = (num - min_val) // bucket_size
        # Bucket index (e.g., (3-1)//2=1)
        bucket_min[bucket_idx] = min(bucket_min[bucket_idx], num)
        # Update min (e.g., min(inf,3)=3)
        bucket_max[bucket_idx] = max(bucket_max[bucket_idx], num)
        # Update max (e.g., max(-inf,3)=3)

    # Line 6: Find maximum gap
    max_gap = 0
    # Max gap found (e.g., 0)
    prev_max = min_val
    # Previous max (e.g., 1)
    for i in range(num_buckets):
        # Scan buckets (e.g., 0 to 2)
        if bucket_min[i] == float('inf'):
            # Empty bucket, skip (e.g., none here)
            continue
        max_gap = max(max_gap, bucket_min[i] - prev_max)
        # Update gap (e.g., max(0,6-3)=3)
        prev_max = bucket_max[i]
        # Update prev (e.g., 6)

    # Line 7: Return maximum gap
    return max_gap
    # e.g., 3

This detailed breakdown clarifies how bucket sort efficiently finds the maximum gap.

Alternative: Sorting with Linear Scan Approach

Explanation

Sorting with Linear Scan sorts the array and scans for the maximum gap:

• Sort nums in ascending order.
• Iterate through consecutive pairs, computing differences.
• Track the maximum difference.

It’s a practical alternative, simple with O(n log n) time (due to sorting), O(1) space (excluding sort space), but doesn’t meet the O(n) requirement.

For [3,6,9,1]:

• Sort: [1,3,6,9].
• Gaps: 2, 3, 3, max=3.

Step-by-Step Example (Alternative)

For [1,5,10,14,15]:

• Step 1: Sort: [1,5,10,14,15].
• Step 2: Gaps: 4, 5, 4, 1, max=5.
• Finish: Return 5.

How the Code Works (Sorting)

def maximumGapSort(nums: list[int]) -> int:
    if len(nums) < 2:
        return 0
    nums.sort()
    max_gap = 0
    for i in range(1, len(nums)):
        gap = nums[i] - nums[i-1]
        max_gap = max(max_gap, gap)
    return max_gap

Complexity

• Bucket Sort:
• Time: O(n) – linear pass with buckets.
• Space: O(n) – bucket arrays.
• Sorting with Linear Scan:
• Time: O(n log n) – sorting dominates.
• Space: O(1) – in-place sort (excluding input).

Efficiency Notes

Bucket Sort is the best solution with O(n) time and O(n) space, meeting the time goal (space often interpreted flexibly)—Sorting with Linear Scan uses O(n log n) time, making it simpler but slower, though space-efficient.

Key Insights

• Bucket Sort: Linear gap finding.
• Sorting: Intuitive but slower.
• Gaps: Successive differences.

Additional Example

For nums = [1,3,100]:

• Goal: 97.
• Bucket: Gaps 2, 97, max=97.

Edge Cases

• Single Element: [1] → 0.
• Two Elements: [1,5] → 4.
• Large Gaps: [1,1000] → 999.

Both solutions handle these well.

Final Thoughts

LeetCode 164: Maximum Gap in Python is a challenging gap-finding problem. The Bucket Sort solution excels with its linear efficiency and cleverness, while Sorting with Linear Scan offers a straightforward approach. Want more? Try LeetCode 148: Sort List for sorting practice or LeetCode 94: Binary Tree Inorder Traversal for tree skills. Ready to practice? Solve LeetCode 164 on LeetCode with [3,6,9,1], aiming for 3—test your skills now!