Maximum Gap

Problem: Maximum Gap

The general idea of solving this problem is operating a rough sorting on our numbers. We establish a hash table and make entries means how much a number bigger than minimum number in the list. We can make maximum gap can only be generated by numbers of adjacent slots.

Code in Python:

class Solution(object):
    def maximumGap(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) < 2:
            return 0

        min_num, max_num, n = min(nums), max(nums), len(nums)
        interval = (max_num - min_num) / n
        if not interval:
            interval = 1
        table = [None] * n

        for num in nums:
            i = min((num-min_num)/interval, n-1)
            if table[i]:
                table[i].append(num)
            else:
                table[i] = [num]

        res = prev = 0
        for i in xrange(1, n):
            if table[i]:
                res = max(res, min(table[i]) - max(table[prev]))
                prev = i

        return res

In this code, numbers in the same slot vary less than interval, and numbers of adjacent slots have chances to generate maximum gap.