Question: https://leetcode.com/problems/maximum-gap/
Question Name: Maximum Gap
The solution uses the bucket sorting and Pigeonhole principle. We divide the input range into bucketCount ranges. Each sub-section has the same length, and the sum of all the sub-sections covers the whole input range. Taking [3,6,8,1] as example, we have four buckets, and each bucket has length of 2. The range of all these buckets is as following: [[9, 0], [9, 0], [9, 0], [9, 0]]. Each [9, 0] is a bucket, with first item being the minimum element and the second item being the maximum value inside this bucket’s range. Initially we set them to an impossible value. Then we put each input item into its buckets.
After putting, there are two possible cases:
One is each bucket contains one and only one integer. In such case, bucket[0] is equal to bucket[1]. And all the input integers are sorted in ascending order (bucket sorting). With [3, 6, 8,1], the final buckets are: [[1, 1], [3, 3], [6, 6], [8, 8]]. We could go through the buckets and compare the adjacent-bucket gap to get the maximum gap.
The other case is that, multiple items follow in one bucket. Therefore there is at least one empty bucket according to Pigeonhole principle. With [1, 2, 3, 8], the result buckets are: [[1, 2], [3, 3], [9, 0], [8, 8]], where the third bucket is empty. In other words, there must be some buckets i and j, such that i + 1 < j. And for all k between i and j, buckets[k] is empty. In such case, there are three kinds of gaps: inside-bucket gap, adjacent-bucket gap, and cross-empty-bucket gap. Inside-bucket gap is always less than or equal to bucketSize, while cross-empty-bucket gap is always greater than bucketSize. As a result, when we compute the maximum gap, we only consider adjacent-bucket gap (like buckets[0] and buckets[1]) and cross-empty-bucket gap (like buckets[1] and buckets[3]).
The full solution is as following:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | class Solution: # @param num, a list of integer # @return an integer def maximumGap(self, num): # Prepare work distinctInputLen = len(set(num)) if distinctInputLen < 2: return 0 maxNum = max(num) minNum = min(num) #Determine the bucket size and count bucketSize = max(1, (maxNum - minNum + 1) // distinctInputLen) bucketCount = (maxNum - minNum + 1) // bucketSize if bucketCount * bucketSize < maxNum - minNum + 1: bucketCount += 1 buckets = [[maxNum+1, minNum-1] for _ in xrange(bucketCount)] # Put the numbers in the buckets. But we only record the # maximum and minmum values inside each bucket. for x in num: pos = (x- minNum) // bucketSize buckets[pos][0] = min(buckets[pos][0], x) buckets[pos][1] = max(buckets[pos][1], x) # Compute the maximum gap maxGap = -1 currentBucket = 0 while currentBucket < bucketCount: if buckets[currentBucket][0] == maxNum+1: # Skip the empty bucket currentBucket += 1 continue # Try to find the next non-empty bucket nextBucket = currentBucket + 1 while nextBucket < bucketCount and buckets[nextBucket][0] == maxNum+1: # Skip the empty bucket nextBucket += 1 if nextBucket == bucketCount: # The currentBucket is the last non-empty bucket break else: # Compute the gap cross adjacent buckets. maxGap = max(maxGap, buckets[nextBucket][0] - buckets[currentBucket][1]) currentBucket = nextBucket return maxGap |