Very simple solution accepted as best in C, well-explained


  • 6

    Actually I just want to use QuickSort and then search for the value which will actually takes quite good performance accepted with 8ms in C -> even size of the list is 2^32 the sorting time will be controlled in O(32n) -> O(nlogn); but of course we should try some other funny solutions also.

    • space cost O(1);
    • time cost O(nlogn) using QuickSort;

    void sort(int* nums, int begin, int end)
    {
        int l=begin, r=end;
        int v = nums[l+(r-l)/2];
        while(l <= r)
        {
            while(nums[l] < v) l++;
            while(nums[r] > v) r--;
            if(l <= r)
            {
                int t = nums[l];
                nums[l] = nums[r];
                nums[r] = t;
                l++; r--;
            }
        }
        if(begin < r)
        sort(nums, begin, r);
        if(l < end)
        sort(nums, l, end);
    }
    
    //AC - 8ms;
    int maximumGap(int* nums, int size) 
    {
        sort(nums, 0, size-1);
        int max = 0;
        for(int i = 1; i < size; i++)
            if(nums[i]-nums[i-1] > max)
                max = nums[i]-nums[i-1];
        return max;
    
    }
    

    Since we are required to solve it in linear time, we have to abandon our lovely QuickSort which really make the whole code quite clean and concise. Using BucketSort is the way or actually another way as other posts mentioned RadixSort which actually I think is just a derivative of BucketSort. Three steps to solve this problem linearly:

    • get the range of the number -> O(n) find the min and max of the numbers; then get the gap within a bucket by gap=(max-min)/(size-1)+1; the bucket will cover [min+k*gap, min+(k+1)*gap) while the left inclusive and the right exclusive; as a result the maximal numbers located in a single bucket will be (max-min)/(size-1) and so there must be a gap between two consecutive numbers are bigger than this average gap -> maximal gap and then located in two different buckets -> that's why we need bucket sorting; if you don't know why, please check Pigeonhole Principle first.

    • map the number into buckets; but we actually only need to store the minimal and maximal value of the bucket since the maximal gap will definitely bigger than the average gap;

    • traverse the buckets to get the maximal gap.

    End of Story!

    • space cost O(n) using space to save time;
    • time cost O(n) actually when the numbers are not that much, this solution can be slower compared with the previous one.

    int maximumGap(int* nums, int size)
    {
        if(size < 2) return 0;
        int min=INT_MAX, max=0;
        for(int i = 0; i < size; i++)
        {
            if(nums[i] < min) min = nums[i];
            if(nums[i] > max) max = nums[i];
        }
        if(min == max) return 0; //some corner cases;
        if(min+1 == max) return 1;
        if(size == 2) return max-min;
        int gap = (max-min)/(size-1)+1; //make later index searching process easier but actually there will be also (max-min)/(size-1) numbers in each bucket;
        int** buckets = (int**)malloc(sizeof(int*)*size); //only store the min and max in the bucket;
        for(int i = 0; i < size; i++)
        {
            buckets[i] = (int*)malloc(sizeof(int)*2);
            buckets[i][0] = -1;
            buckets[i][1] = 0;
        }
        for(int i = 0; i < size; i++) //[min+k*gap, min+(k+1)*gap);
        {
            int k = (nums[i]-min)/gap; //get the index of the bucket;
            if(nums[i] > buckets[k][1]) //the greatest in the bucket;
                buckets[k][1] = nums[i];
            if(buckets[k][0]==-1 || nums[i]<buckets[k][0]) //store the minimal in the kth gap;
                buckets[k][0] = nums[i];
        }
        int start = buckets[0][1];
        int end = buckets[0][0];
        int maxGap = 1;
        for(int i = 0; i < size; i++)
        {
            if(buckets[i][0] > end) //move to the next bucket that has numbers since we initialize bucket with -1 and 0;
            {
                end = buckets[i][0]; //the end of the gap;
                if(end-start > maxGap)
                    maxGap = end-start;
                start = buckets[i][1]; //move to the next start;
            }
        }
        return maxGap;
    }

  • 0

    Your deterministic quick sort is not guaranteed to be O(n.logn).


  • 0

    @babhishek21 Er, strictly speaking almost all solutions have the worst cases, so here you are trying to be particular about that kind of cases?


  • 0

    @LHearen I was specifically speaking about your implementation of quicksort. You used a deterministic pivot. That's not even going to guarantee an expected O(n.logn) runtime. Had you used a randomised pivot, you could claim that. That's all I am saying.


  • 0

    ... then get the gap within a bucket by gap=(max-min)/(size-1)+1; the bucket will cover [min+k*gap, min+(k+1)*gap) while the left inclusive and the right exclusive; as a result the maximal numbers located in a single bucket will be (max-min)/(size-1) and so there must be a gap between two consecutive numbers are bigger than this average gap -> maximal gap and then located in two different buckets -> that's why we need bucket sorting; ...

    Can someone explain this please?


  • 0

    @babhishek21 Your point is clear now. But did you really try its performance and just theoretically talking about it? As far as I tried it for 1000 times by local script using 1 million to 10 million random arrays, it turned out its performance is acceptable.


  • 0

    @LHearen Only theoretically


Log in to reply
 

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