We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Gap

Number: 164

Difficulty: Medium

Paid? No

Companies: Bloomberg, Google, DoorDash, Adobe

Problem Description

Given an integer array nums, determine the maximum difference between any two successive elements in its sorted form. If the array has fewer than two elements, return 0. The challenge is to achieve a solution that runs in linear time and uses linear extra space.

Key Insights

  • Sorting the array explicitly would take O(n log n) time, which is not acceptable; instead, we can use an optimal bucket sort-based approach.
  • The idea is to determine the minimum and maximum values in the array.
  • The maximum gap will occur not within a bucket but between adjacent buckets.
  • Compute appropriate bucket size (gap) and then distribute numbers across these buckets.
  • Track the minimum and maximum value within each bucket.
  • The maximum gap is the maximum difference between the minimum value of the current non-empty bucket and the maximum value of the previous non-empty bucket.

Space and Time Complexity

Time Complexity: O(n) Space Complexity: O(n)

Solution

The solution involves these steps:

  1. Find the minimum and maximum value in the array. If they are equal, return 0 because all numbers are the same.
  2. Compute the bucket size using the formula: bucket_size = max(1, (max_val - min_val) / (n - 1)).
  3. Calculate the number of buckets required: bucket_count = (max_val - min_val) / bucket_size + 1.
  4. Initialize each bucket to store its minimum and maximum values.
  5. Iterate over the array and place each element in its corresponding bucket.
  6. Finally, iterate through the buckets and compute the maximum gap by comparing the minimum value of the current non-empty bucket with the maximum value of the previous non-empty bucket.

This bucket-based strategy ensures that the maximum gap is found without performing a full sort, maintaining linear time complexity.

Code Solutions

# Python solution for Maximum Gap
def maximum_gap(nums):
    # If there are fewer than 2 elements, return 0
    if len(nums) < 2:
        return 0

    # Find the minimum and maximum values in the array
    min_val, max_val = min(nums), max(nums)
    if min_val == max_val:
        return 0  # All numbers are the same

    # Calculate the bucket size using a ceiling division method, ensuring at least 1
    n = len(nums)
    bucket_size = max(1, (max_val - min_val) // (n - 1))
    bucket_count = (max_val - min_val) // bucket_size + 1

    # Initialize buckets where each bucket holds [min_value, max_value]
    buckets = [[None, None] for _ in range(bucket_count)]

    # Distribute the numbers into the buckets
    for num in nums:
        # Identify the index for the bucket this number belongs to
        idx = (num - min_val) // bucket_size
        # Update bucket's min and max values
        if buckets[idx][0] is None:
            buckets[idx][0] = num
            buckets[idx][1] = num
        else:
            buckets[idx][0] = min(buckets[idx][0], num)
            buckets[idx][1] = max(buckets[idx][1], num)

    # Compute the maximum gap from the buckets.
    max_gap = 0
    previous_max = None

    for b in buckets:
        # Ignore empty buckets
        if b[0] is None:
            continue
        if previous_max is not None:
            max_gap = max(max_gap, b[0] - previous_max)
        previous_max = b[1]

    return max_gap

# Example usage:
print(maximum_gap([3, 6, 9, 1]))  # Output: 3
print(maximum_gap([10]))          # Output: 0
← Back to All Questions