Solutions in C++ with explanation, read it and then you get it


  • 6

    Solutions

    When first coming into this problem, the first direct idea is to sort it and then search for the maximal difference along the array. And as a result we will have a sort solution as follows.

    Sort

    Very straightforward solution via sorting using O(1) space while efficient enough time cost O(nlogn).

    int maximumGap(vector<int>& nums) 
    {
    	int size = nums.size();
    	if(size < 2) return 0;
    	if(size == 2) return abs(nums[1]-nums[0]);
    	int maxDiff = 0;
    	sort(nums.begin(), nums.end());
    	for(int i = 0; i < size-1; ++i)
    		maxDiff = max(maxDiff, nums[i+1]-nums[i]);
    	return maxDiff;
    }
    

    Bucket

    But sorting the whole array is really costly since it's quite unnecessary to sort them all when just trying to find out the maximal difference between successive two numbers in its sorted state. So quite intuitively we would like to use bucket sort to accelerate the process, another typical case using space to accelerate. Why using bucket? If we can set a proper size for each bucket to ensure the maximal difference definitely comes from two different buckets then we do not need to sort the whole array, just checking the minimal and maximal number of each bucket from small to big buckets - ascending order. But how to select the right size for each bucket?

    Before reading the analysis below, please do remember the following rule.

    • ensure the maximal difference comes from different buckets

    Here are some analysis about it:

    1. since we are to adopt bucket here, we have to first retrieve the max and min number of the array;
    2. the array with size numbers will split the [min, max] space into size-1 different blocks so the numbers of the array will lie in [min, min+gap), [min+gap, min+2*gap), ..., [min+(size-2)*gap, min+(size-1)*gap) by the way the gap here is the size of the block which we will discuss further later; the blocks here are the buckets we mentioned
    3. via the ranges of buckets, we can easily locate the bucket-index of any number in the array by (num-min)/gap and also simply let's get the answer of the size of the bucket (max-min)/(size-1)+1 but how to get the size exactly? We still have no clue.
    4. normally the average distance between two numbers should be (max-min)/(size-1) but the maximal difference here must be no less than that (why? Just imagine if the max difference is less than the average, how come the average is so big here?) as we have discussed in 2, the maximal difference within a bucket will be gap-1 (take the first range [min, min+gap) for an example, then the min+gap-1-min = gap-1 is the difference within the bucket) so here we should set the size of bucket as (max-min)/(size-1)+1 to split the array then the maximal difference within a bucket will be (max-min)/(size-1) but when we can divide (max-min) completely by (size-1), the case will be different?

    Take an example to make it easier here:
    [1, 2, 3, 4, 21] so max = 21, min = 1, size = 5 => (max-min)/(size-1)+1 = 20/4+1 = 6
    so as a result the ranges of buckets are [1, 7), [7, 13), [13, 19), [19, 25)

    • the maximal difference within a bucket now is 5, which is the average distance and we have discussed it already
    • all the numbers in the array are covered including the min and max
    • even when the array is [1, 6, 11, 16, 21] the maximal difference still can be retrieved from different buckets here.

    When we can not completely divide (max-min) by (size-1) and there is remainder, the case will be still the same and even clearer.

    1. since we get the most tricky part done then let's just solve it step by step; remember we are going to retrieve the maximal difference from different buckets? So we only need to record the min and max of the bucket instead of all the numbers inside here;
    2. after filling up the buckets, we now can retrieve the maximal from the first till the end.

    The final solution in C++ is as follows, of course the best submission here, since it's hard to read all the things above. Enjoy now...

    int maximumGap(vector<int>& nums) 
    {
        int size = nums.size();
        if(size < 1) return 0;
        if(size == 2) return abs(nums[1]-nums[0]);
        int minNum = INT_MAX, maxNum = INT_MIN;
        for(int i = 0; i < size; ++i) minNum = min(minNum, nums[i]), maxNum = max(maxNum, nums[i]);
        if(minNum == maxNum) return 0;
        int gap = (maxNum-minNum)/(size-1)+1;
        int mins[size], maxs[size]{0};
        for(int i = 0; i < size; ++i) mins[i] = -1;
        for(int i = 0; i < size; ++i)
        {
            int k = (nums[i]-minNum)/gap;
            if(mins[k] == -1) mins[k] = nums[i];
            else mins[k] = min(mins[k], nums[i]);
            maxs[k] = max(maxs[k], nums[i]);
        }
        int start = maxs[0], end = mins[0];
        int maxGap = start-end;
        for(int i = 1; i < size; ++i)
        {
            if(mins[i] != -1)
            {
                maxGap = max(maxGap, mins[i]-start);
                start = maxs[i];
            }
        }
        return maxGap;
    }
    

    Always welcome new ideas and practical tricks, just leave them in the comments!


  • 0
    C

    why int mins[size], maxs[size]{0};? a little confused. why not int mins[size/gap+1]?
    Thanks


  • 0

    @Chengcheng.Pei Okay, you just don't get it. The max and min of the array will be splitted into (max-min)/(size-1)+1 buckets so it should be int mins[size], maxs[size]{0}; As for why it should be splitted like that, check the explanation above. Have fun!


  • 0
    S

    @LHearen What is the time complexity of the bucket sort approach? It looks like O(n). Am i right?
    TIA


  • 0

    @SandeepKV That's correct and that's what required also.


  • 0
    D

    I have some question about the time complexity about the bucket sort. I think the O(n) time complexity of bucket sort is achieved only when we set bucket to max - min, am i right?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.