maximum gap

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)

//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;
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;

if(buckets[i].first != -1)
int temp_min=buckets[i].first;
if((temp_min – minVal) >max_diff)
max_diff=temp_min – minVal;

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;
return max_diff;


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

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

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.