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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Gap

Difficulty: Medium

Problem Description

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.

Key Insights

  • The maximum gap can be effectively found without fully sorting the array.
  • We can use a bucket sort approach to ensure that we find the maximum gap in linear time.
  • The number of buckets will be determined by the range of the numbers and the number of elements in the array.
  • Each bucket will store the minimum and maximum values of the elements that fall into it, enabling efficient gap calculation.

Space and Time Complexity

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

Solution

To solve the problem, we will use the following steps:

  1. Edge Case Handling: If the length of the array is less than 2, return 0 immediately.
  2. Find Minimum and Maximum: Determine the minimum and maximum values in the array to understand the range of numbers.
  3. Bucket Initialization: Create buckets to hold the minimum and maximum values. The number of buckets is derived from the range of numbers divided by the size of the array.
  4. Distribute Numbers into Buckets: Place each number into the corresponding bucket based on its value.
  5. Calculate Maximum Gap: Iterate through the buckets to find the maximum gap between the maximum of one bucket and the minimum of the next bucket.

Code Solutions

def maximumGap(nums):
    if len(nums) < 2:
        return 0
    
    min_num, max_num = min(nums), max(nums)
    if min_num == max_num:
        return 0
    
    n = len(nums)
    bucket_size = max(1, (max_num - min_num) // (n - 1))  # Size of each bucket
    bucket_count = (max_num - min_num) // bucket_size + 1  # Number of buckets
    
    # Initialize buckets
    buckets = [[float('inf'), float('-inf')] for _ in range(bucket_count)]
    
    # Place numbers into buckets
    for num in nums:
        idx = (num - min_num) // bucket_size
        buckets[idx][0] = min(buckets[idx][0], num)
        buckets[idx][1] = max(buckets[idx][1], num)
    
    # Calculate maximum gap
    max_gap = 0
    previous_max = min_num
    
    for bucket in buckets:
        if bucket[0] == float('inf'):  # Empty bucket
            continue
        max_gap = max(max_gap, bucket[0] - previous_max)
        previous_max = bucket[1]
    
    return max_gap
← Back to All Questions