'''
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:
    # @param num, a list of integer
    # @return an integer
    def maximumGap(self, num):
        n = len(num)
        if n<2: return 0
        maxnum = num[0]; minnum = num[0]
        for i in xrange(n):
            minnum = min(num[i],minnum)
            maxnum = max(num[i],maxnum)
        
        bucket_size = (maxnum-minnum-1)/(n-1)+1
        bucket_min_max = [(float('inf'), float('-inf')) for i in xrange(n)]
        
        for i in xrange(n):
            index = (num[i]-minnum)/bucket_size
            bucket_min_max[index]=(min(bucket_min_max[index][0],num[i]),max(bucket_min_max[index][1],num[i]))
        
        gap = 0
        premax = bucket_min_max[0][1]
        for bucket_min, bucket_max in bucket_min_max[1:]:
            if bucket_min == float('inf'):
                continue 
            gap = max(bucket_min - premax, gap)
            premax = bucket_max
            
        return gap
        
# test case: [1,1000000], 
# Reference: https://leetcode.com/discuss/18499/bucket-sort-java-solution-with-explanation-o-time-and-space
# 这道题目的思路是：对于给定的区间[imin, imax],the max gap between the numbers should not smaller than ceiling[(imax-imin)/(n-1)]
# for example: [1,2,3,4,5,6,7,8,9], 如果给定的个数为3，区间为1到9，最小的gap为4，任意取3个数，会发现最小gap肯定为4
# 我们取n个bucket，所以第kth bucket contains numbers in [min+(k-1)gap, min + k* gap]
# Basically we argue that the largest gap can not be smaller than (max-min)/(N-1), 
# so if we make the buckets smaller than this number, any gaps within the same bucket is not the amount we are looking for, 
# so we are safe to look only for the inter-bucket gaps.

Create Maximum_Gap.py