Maximum Distance Between A Pair Of Values - Leetcode Solution

Problem Description:

Given an array of integers nums sorted non-decreasingly, find the maximum distance between any pair of elements in the array.

Return the maximum distance.

If the array is empty, return 0.

Solution:

The approach is to use the bucket sorting technique to find the maximum distance between two elements in the array. Bucket sorting is a linear sorting algorithm that distributes elements of an array into a number of buckets/bins. Then each bucket is sorted, and the sorted elements are combined.

The steps to solve this problem are as follows:

1. Determine the minimum and maximum values of the array.

2. Compute the size of each bucket, which is equal to (max_val - min_val) / (n - 1), where n is the length of the array.

3. Create n-1 buckets and distribute the elements into them based on their value.

4. Initially, the minimum and maximum values of the last non-empty bucket are set to the values of the first element of that bucket.

5. For each non-empty bucket, update the maximum value as the difference between the current element and the minimum value of the bucket and update the minimum value as the current element's value.

6. The maximum difference between any two elements is the maximum value of the non-empty buckets.

Here is the code implementation of the above approach:

class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        if not nums or len(nums) < 2:
            return 0

        n = len(nums)
        min_val, max_val = min(nums), max(nums)
        if min_val == max_val:
            return 0

        bucket_size = max(1, (max_val - min_val) // (n - 1))
        bucket_n = (max_val - min_val) // bucket_size + 1
        bucket_min = [float('inf')] * bucket_n
        bucket_max = [float('-inf')] * bucket_n

        for num in nums:
            bucket_i = (num - min_val) // bucket_size
            bucket_min[bucket_i] = min(bucket_min[bucket_i], num)
            bucket_max[bucket_i] = max(bucket_max[bucket_i], num)

        max_gap = 0
        last_max = min_val
        for i in range(bucket_n):
            if bucket_min[i] == float('inf'):
                continue
            max_gap = max(max_gap, bucket_min[i] - last_max)
            last_max = bucket_max[i]

        return max_gap

Time Complexity:

The time complexity of the above algorithm is O(n), where n is the length of the array. The bucket distribution takes O(n), and the bucket sorting takes O(bucket_size * bucket_n), which is less than or equal to O(n) because we have n-1 buckets with at least one element.

Space Complexity:

The space complexity of the above algorithm is O(n), where n is the length of the array, because we use two arrays representing the minimum and maximum values for each bucket.

1