- 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).

1 | int maximumGap(vector<int>& nums) { |

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.

1 | int maximumGap(vector<int>& nums) { |

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.

1 | class Solution { |

https://discuss.leetcode.com/topic/5996/i-solved-it-using-radix-sort

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?

1 | class Solution: |

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

Beat 99.81% java coder

1 | public int maximumGap(int[] nums) { |

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.

1 | class Solution { |

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) ]

1 | #include <iostream> |

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

My concise and short c++ code with comment explanation

1 | int maximumGap(vector<int>& nums) { |

[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

1 | public class Solution { |

https://discuss.leetcode.com/topic/22221/radix-sort-solution-in-java-with-explanation

Radix sort solution in Java with explanation

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

https://www.cs.usfca.edu/~galles/visualization/RadixSort.html

1 | public class Solution { |

- The first step is to find the maximum value in nums array, it will be the threshold to end while loop.
- Then use the radix sort algorithm to sort based on each digit from Least Significant Bit (LSB) to Most Significant Bit (MSB), that’s exactly what’s showing in the link.
- (nums[i] / exp) % 10 is used to get the digit, for each digit, basically the digit itself serves as the index to access the count array. Count array stores the index to access aux array which stores the numbers after sorting based on the current digit.
- Finally, find the maximum gap from sorted array.

Time and space complexities are both O(n). (Actually time is O(10n) at worst case for Integer.MAX_VALUE 2147483647)