[Leetcode] 164. Maximum Gap

A really smart solution using pigeon hole principle and bucket sort...

---

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

---

class Solution(object):
    def maximumGap(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums: return 0
        min_v, max_v = min(nums), max(nums)
        if min_v == max_v: return 0
        
        buckets = [[] for _ in range(len(nums)+1)]
        for num in nums:
            bkt = (num - min_v) * len(nums) / (max_v - min_v)
            buckets[bkt].append(num)
        
        i = 0
        res = 0
        while i < len(buckets) - 1:
            k = i + 1
            while len(buckets[k]) == 0:
                k = k + 1
            res = max(res, min(buckets[k]) - max(buckets[i]))
            i = k
        return res