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


  • 22
    D

    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.

    class Solution {
    public:
    int maximumGap(vector<int> &num) {
    int sSize = num.size();
    int i, res =0;
    int minV, maxV;
    int bucket_size, bucket_num, bucket_id;
    int maxGap = INT_MIN;
    int last_max;

        if(sSize>1)
        {
            minV =  maxV = num[0];
            for(i=1; i<sSize; i++)
            {
                if(minV > num[i]) minV = num[i];
                else if(maxV < num[i]) maxV = num[i];
            }
            
            bucket_size = max(1, (maxV - minV )/ (sSize - 1)));
            bucket_num  = (maxV - minV)/bucket_size + 1;
    
            if(bucket_num <=1) return (maxV - minV); 
            vector<int> bucket_max(bucket_num, INT_MIN);
            vector<int> bucket_min(bucket_num, INT_MAX);
            vector<int> bucket_count(bucket_num, 0);
            
            for(i=0; i<sSize; i++)
            {
                bucket_id = (num[i] - minV)/bucket_size;
                bucket_count[bucket_id]++;
                bucket_min[bucket_id] = bucket_min[bucket_id] > num[i]? num[i]:bucket_min[bucket_id];
                bucket_max[bucket_id] = bucket_max[bucket_id] < num[i]? num[i]:bucket_max[bucket_id];
            }
            
            last_max = minV;
            for(i=0; i<bucket_num; i++)
            {
                if(bucket_count[i]>0)
                {
                    maxGap = max(maxGap, bucket_min[i]- last_max);
                    last_max = bucket_max[i];
                }
            }
            return maxGap;
        }
        return 0;
    }
    

    };


  • 0
    A

    Works without :
    maxGap = max(maxGap, bucket_max[i]- bucket_min[i]);


  • 0
    D

    Thanks for pointing that out. You are absolutely right and the code is updated as suggested.


  • 2
    P

    You dont need bucket_count, you can simply check with INT_MIN and INT_MAX. Otherwise, nice solution. Example :

                if (bucketMin[i] != INT_MAX) {
                    maxGap = max(bucketMin[i]-last_max, maxGap);
                } 
                if (bucketMax[i] != INT_MIN) {
                    last_max = bucketMax[i];
                }
    

  • 0
    C

    don't need indeed ,because lower bound of the gap is (maxV - minV )/ (sSize - 1)


Log in to reply
 

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