Solution to Maximum Gap by LeetCode

6 Apr


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:


Leave a Reply

Your email address will not be published. Required fields are marked *