Leetcode: Maximum Gap (16ms)

PROBLEM:

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.

------------------------------------------------------

------------------------------------------------------

Using bucket sort.
assign the value one by one to the related bucket with index 'id'= (x-min)/ave_gap;
it's possible a bucket contain more than 2 values, only keep the minimal and maximal value. 

////////////////////////////////////////////////////////////

//CODES

class Solution {

public:

       int maximumGap(vector<int>& nums) {

              //check input

              if (nums.size() == 0 || nums.size() == 1) return 0;

              //find out the min and max

              int Min = nums[0], Max = nums[0];//Min=INT_MAX, Max=INT_MIN;

              for (auto x : nums){

                     Min = Min<x ? Min : x;

                     Max = Max>x ? Max : x;

              }

              //gap, take ceiling

              int gap = ceil((Max - Min) / (nums.size() - 1))+1;

              //put to buckets

              vector<vector<int>> buckets(nums.size() - 1);

              for (auto x : nums){

                     int idx = (x - Min) / gap;//get index for buckets

                     if (buckets[idx].empty()){

                           buckets[idx].reserve(2);

                           buckets[idx].push_back(x);

                           buckets[idx].push_back(x);

                     }

                     else{

                           if (x < buckets[idx][0]) buckets[idx][0] = x;

                           if (x > buckets[idx][1]) buckets[idx][1] = x;

                     }

              }

              //find max gap

              int pre = 0, cur = 0, mgap = 0;

              if (buckets.size()>1){

                     for (int i = 1; i<buckets.size() ; i++){

                           if (buckets[i].empty()) continue;

                           cur = buckets[i][0];

                           mgap = cur - buckets[pre][1]>mgap ? cur - buckets[pre][1] : mgap;

                           pre = i;

                           //if (buckets[i][1] == Max)break;

                     }

              }

              else{

                     mgap = buckets[0][1] - buckets[0][0];

              }

              return mgap;

       }

};