164. Maximum Gap Leetcode Java

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.

Solution:

Non-linear time solution. Sort the array and check the gap one by one. O(nlogn).

Linear time solution: Bucket sort.

Assume there are n elements in this array, and the maximum gap must be greater than (max-min)/n-1. Otherwise min+sum(gap[i])<=min+(n-1)*maxGap<max, which is a contradiction.

Therefore, we can divide all elements into (n-1) buckets, and the length of the bucket will be (max-min)/n-1. Since maxGap> (max-min)/n-1, so the two elements that generate the biggest gap must come from two different buckets. For each element in the array, we can easily determine which bucket it located and thus we can maintain a minimumValue and maximumValue for each bucket. By checking bucket[i+1].minValue-bucket[i].maximumValue, we can find the maximum gap.

 public int maximumGap(int[] num) {  
    if(num==null || num.length<2) return 0;  
    int min=Integer.MAX_VALUE;  
    int max=0;  
    for(int i=0;i<num.length;i++){  
      min=Math.min(min,num[i]);  
      max=Math.max(max,num[i]);  
    }  
    int res=(max-min-1)/(num.length-1)+1;  
    int gap=res;  
    int[] minBucket=new int[num.length];  
    for(int i=0;i<num.length;i++) minBucket[i]=max;  
    int[] maxBucket=new int[num.length];  
    for(int i=0;i<num.length;i++){  
      int ind=(num[i]-min)/gap;  
      minBucket[ind]=Math.min(minBucket[ind],num[i]);  
      maxBucket[ind]=Math.max(maxBucket[ind],num[i]);  
    }  
    int pre=0;  
    for(int i=1;i<num.length;i++){  
      if(maxBucket[i]!=0){  
      res=Math.max(res,minBucket[i]-maxBucket[pre]);  
      pre=i;  
      }  
    }  
    return res;  
   }