maximum-gap

Try it on leetcode

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.

You must write an algorithm that runs in linear time and uses linear extra space.

 

Example 1:

Input: nums = [3,6,9,1]
Output: 3
Explanation: The sorted form of the array is [1,3,6,9], either (3,6) or (6,9) has the maximum difference 3.

Example 2:

Input: nums = [10]
Output: 0
Explanation: The array contains less than 2 elements, therefore return 0.

 

Constraints:

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 109

Solution(Python)

class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        return self.bucketSort(nums)
    #Time Complexity: O(n^2)
    # Space Complexity: O(1)
    def naiveApproach(self, nums: List[int]) -> int:
        max_diff = 0
        nums.sort()
        n = len(nums)
        for i in range(1, n):
            max_diff = max(max_diff, nums[i]-nums[i-1])
        return max_diff
     
    #Time Complexity: O(n+K)
    # Space Complexity: O(K)
    def countingSortApproach(self, nums: List[int]) -> int:
        min_val, max_val = min(nums), max(nums)
        count = [0] * (max_val - min_val + 1)
        
        for num in nums:
            count[num-min_val]+=1
        result = []
        for i, c in enumerate(count):
            result.extend([i + min_val] * c)
        max_diff = 0
        n = len(nums)
        for i in range(1, n):
            max_diff = max(max_diff, result[i]-result[i-1])
        return max_diff
    
    def radixSort(self, nums: List[int]) -> int:
        if len(nums) < 2:
            return 0

        maxVal = max(nums)
        exp = 1
        radix = 10
        aux = [0] * len(nums)

        while maxVal // exp > 0:
            count = [0] * radix
            for num in nums:
                count[(num // exp) % 10] += 1
            for i in range(1, radix):
                count[i] += count[i - 1]
            i = len(nums) - 1
            while i >= 0:
                aux[count[(nums[i] // exp) % 10] - 1] = nums[i]
                count[(nums[i] // exp) % 10] -= 1
                i -= 1
            for i in range(len(nums)):
                nums[i] = aux[i]
            exp *= 10

        maxGap = 0
        for i in range(len(nums) - 1):
            maxGap = max(nums[i + 1] - nums[i], maxGap)
        return maxGap
    
     #Time Complexity: O(n)
    # Space Complexity: O(n)   
    def bucketSort(self, nums):
        if len(nums) < 2:
            return 0

        mini, maxi = min(nums), max(nums)

        bucketSize = max(1, (maxi - mini) // (len(nums) - 1))
        bucketNum = (maxi - mini) // bucketSize + 1
        buckets = [Bucket() for _ in range(bucketNum)]

        for num in nums:
            idx = (num - mini) // bucketSize
            buckets[idx].used = True
            buckets[idx].minval = min(num, buckets[idx].minval)
            buckets[idx].maxval = max(num, buckets[idx].maxval)

        prevBucketMax = mini
        maxGap = 0
        for bucket in buckets:
            if not bucket.used:
                continue

            maxGap = max(maxGap, bucket.minval - prevBucketMax)
            prevBucketMax = bucket.maxval

        return maxGap
    
class Bucket:
    def __init__(self):
        self.used = False
        self.minval = float("inf")
        self.maxval = float("-inf")