• 28.9%

https://leetcode.com/problems/maximum-gap/?tab=Description

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.

https://discuss.leetcode.com/topic/13172/pigeon-hole-principle

Pigeon hole principle

Suppose you have n pigeons with labels and you put them into m holes based on their label with each hole of the same size. Why bother putting pigeons into holes? Because you want to disregard the distance between pigeons within each one hole.

Only when at least one hole is empty can we disregard the distance between pigeons within each one hole and compute the maximum gap solely by the distance between pigeons in adjacent holes. We make sure that at least one hole is empty by using m=n-1 (i.e. n-2 pigeons in n-1 holes => at least one hole is empty).

https://discuss.leetcode.com/topic/13172/pigeon-hole-principle/2

Great idea, get the essence of the problem. I’ll add some more explanations.

We divide the range of array into array.size() interval, where k = (maximum-minimum) / n.

[minimum, minimum + k), [minimum + k, minimum + 2k), … , [minimum + (n-1)k, maximum]

And we uses two extra array “max_in_interval” and “min_in_interval” to record the maximum and minimum of each interval.

First, let’s considering an uniformly distributed array of n numbers. By which I mean,

[minimum, minimum + k), [minimum + k, minimum + 2k), … , [minimum + (n-1)k, maximum]

n intervals each contains a single number. we could easily find the maximum gap by calculate min_in_interval[i+1] - max_in_interval[i]

Now comes the most important observation. If any single interval contains more than 1 number, then there must be an empty interval, and maximum gap is larger than a single interval. By which I mean if multiple numbers appear in the same interval, we can safely ignore the numbers which lies in the middle of interval(not max_in_interval nor min_in_interval).

Below comes my 16ms C++ AC solution.

This is a minor defeact in it, but the test case does not catch it. I uses INT_MAX as a sentinel which should fails if the input array contains it as an element.

https://discuss.leetcode.com/topic/9986/my-c-code-12-ms-bucket-sort-o-n-time-and-space

My C++ code (12 ms, “bucket sort”, O(n) time and space)

The key is to use the fact that the lower bound of the gap is (maxV - minV )/ (sSize - 1). With such in mind, we can put all the num elements into different bucket with size (maxV - minV )/ (sSize - 1) (please note when such size is less than 1, then use 1 instead) and in such way, we only need to consider the min and max of each bucket and don’t need to worry the numbers in between of each bucket since the gaps among those elements are smaller than the bucket size, and then the lower bound of the gap, so they can not achieve the max gap.

I solved it using radix sort

Since linear time and space is required and all nums are non-negative, radix sort seems to be fit.
Here is the implementation.

Any better ideas?

https://discuss.leetcode.com/topic/41228/beat-99-81-java-coder

Beat 99.81% java coder

https://discuss.leetcode.com/topic/21003/12ms-c-suggested-solution

12ms C++ Suggested Solution

This problem has a naive solution using sort and linear scan. The suggested solution uses the idea of bucket sort. The following is a C++ implementation of the suggested solution.

Suppose all the n elements in nums fall within [l, u], the maximum gap will not be smaller than gap = (u - l) / (n - 1). However, this gap may become 0 and so we take the maximum of it with 1 to guarantee that the gap used to create the buckets is meaningful.

Then there will be at most m = (u - l) / gap + 1 buckets. For each number num, it will fall in the k = (num - l) / gap bucket. After putting all elements of nums in the corresponding buckets, we can just scan the buckets to compute the maximum gap.

The maximum gap is only dependent on the maximum number of the current bucket and the minimum number of the next neighboring bucket (the bucket should not be empty). So we only store the minimum and the maximum of each bucket. Each bucket is initialized as {minimum = INT_MAX, maximum = INT_MIN} and then updated while updating the buckets.

Putting these together, we can have the following solution, barely a straight-forward implementation of the suggested solution.

https://discuss.leetcode.com/topic/34414/clean-c-implementation-of-3-linear-time-sort-alg-with-detailed-explaination

Clean C++ implementation of 3 linear-time-sort-alg with detailed explaination

As we can see, we should grasp all the 3 typical linear-time-sorting algorithm implementation.
All the following 3 implementations have been modified from the GeeksForGeeks.
I have change the counting sort implementation to support negative numbers.
And the bucket support any float array input.

counting sort [ stable ] [ support:+/- intergers ]

radix sort [ use counting sort as sub-routine] [ support only
positive intergers]

bucket sort [support float : we need to change the array to in the
range [0, 1) ]

https://discuss.leetcode.com/topic/14353/my-concise-and-short-c-code-with-comment-explanation

My concise and short c++ code with comment explanation

https://discuss.leetcode.com/topic/5999/bucket-sort-java-solution-with-explanation-o-n-time-and-space

[bucket sort] JAVA solution with explanation, O(N) time and space

Suppose there are N elements in the array, the min value is min and the max value is max. Then the maximum gap will be no smaller than ceiling[(max - min ) / (N - 1)].

Let gap = ceiling[(max - min ) / (N - 1)]. We divide all numbers in the array into n-1 buckets, where k-th bucket contains all numbers in [min + (k-1)gap, min + k*gap). Since there are n-2 numbers that are not equal min or max and there are n-1 buckets, at least one of the buckets are empty. We only need to store the largest number and the smallest number in each bucket.

After we put all the numbers into the buckets. We can scan the buckets sequentially and get the max gap.
my blog for this problem

Radix sort solution in Java with explanation

You can look at radix sort visualization here before reading the code: