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

int maximumGap(vector &num) {

if (num.size() < 2) return 0;

int minVal=INT_MAX,maxVal=-1,local_min=INT_MIN,local_max=-1;

int size=num.size();

vector::iterator it;

//get the max and min value

for( it=num.begin() ; it!=num.end();it++)

{

if(*it < minVal) { minVal=*it; } if(*it >maxVal)

{

maxVal=*it;

}

}

//Slot Size is the number of elements in each bucket

int slotsSize= (maxVal-minVal)/(size-1);

//total number of buckets

int numbuckets=(maxVal-minVal)/slotsSize;

//pair is used for max and min

vector<pair<int, int> > buckets(numbuckets, make_pair(-1, -1));

// assign max and min for each bucket

for( it=num.begin() ; it!=num.end();it++)

{

int val=*it;

int bucketNum=(val-(minVal+1))/slotsSize;

if(val != minVal && val !=maxVal)

{

if (buckets[bucketNum].first == -1)

buckets[bucketNum].first = val;

else

buckets[bucketNum].first = min(buckets[bucketNum].first, val);

buckets[bucketNum].second = max(buckets[bucketNum].second, val);

}

}

int max_diff=0;

bool first_time=true;

for(int i=0 ; i < numbuckets;i++) { if(i==numbuckets-1 ) { int x=i; while(buckets[x].first == -1) { x–; } int temp_max=buckets[x].second; if((maxVal- temp_max ) > max_diff)

max_diff=maxVal- temp_max;

break;

}

if(buckets[i].first != -1)

{

if(first_time)

{

int temp_min=buckets[i].first;

if((temp_min – minVal) >max_diff)

max_diff=temp_min – minVal;

first_time=false;

}

for(int j=i+1 ; j <numbuckets;j++) { // If next bucket is non empty if(buckets[j].first != -1) { int temp_max=buckets[i].second; int temp_min=buckets[j].first; if((temp_min – temp_max) >max_diff)

max_diff=temp_min – temp_max;

break;

}

}

}

}

return max_diff;

}

An alternative to above solution:(c++ 11)

http://www.cnblogs.com/skysand/p/4179099.html

# Resolving technical problems:

Solve your technical problems instantly

We provide Remote Technical Support from Monday to Sunday, 7:00PM to 1:00 AM

Mail your problem details at writeulearn@gmail.com along with your mobile numberand we will give you a call for further details. We usually attend your problems within 60 minutes and solve it in maximum 2 days.