Leetcode 164: Maximum Gap

https://leetcode.com/problems/maximum-gap/

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.

 

Code

import sys
import math

class Solution(object):
    def maximumGap(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums or len(nums) < 2:
            return 0
        
        # find max and min in nums
        max_num = -sys.maxint
        min_num = sys.maxint
        for i in nums:
            if i > max_num:
                max_num = i
            if i < min_num:
                min_num = i
        
        if max_num == min_num:
            return 0
        
        bucket_max = [None for _ in xrange(len(nums)+2)]  
        bucket_min = [None for _ in xrange(len(nums)+2)] 
        for i in nums:
            # max_num is actually assigned to n+2-th bucket  
            bucket = ((i-min_num) * (len(nums)+1)) / (max_num - min_num)  
            bucket_max[bucket] = max(bucket_max[bucket], i) if bucket_max[bucket] is not None else i
            bucket_min[bucket] = min(bucket_min[bucket], i) if bucket_min[bucket] is not None else i
        
        max_gap = 0
        prev_max = bucket_max[0]       # the first bucket must have one element
        for i in xrange(1, len(bucket_min)):
            if bucket_min[i] is not None:
                max_gap = max(bucket_min[i] - prev_max, max_gap)
                prev_max = bucket_max[i]
            
        return max_gap

 

Idea

This is a problem using the classic ideas of bucketing and pigeon hole principle. The logic is that, we create `n+1` buckets between `max_num` and `min_num`, where `max_num` and `min_num` of the array can be found in O(N) time. Since there are only `n` numbers in the array, there must be at least one bucket without any number landing in it. This important factor indicates that the max distance of two consecutive numbers in the sorted form must happen between the maximal number in one previous bucket and the minimal number in one latter bucket and the two buckets have at least one empty bucket between them. Any numbers falling into the same bucket will not have the difference exceeding the bucket range, which is `(max_num-min_num)/(n+1)`.