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

Solution 1: As request for O(n) time and O(n) space. Use bracket. The max gap must be greater than gap=(max-min)/(n-1). So we can create n bracket: [min,min+gap), [min+gap,min+2gap).... the result must be value between brackets instead of within bracket. So first step is allocate all numbers into the bracket, then iterate the bracket to find max inter-bracket value.

 public class Solution {  
   public int maximumGap(int[] nums) {  
     int n=nums.length;  
     if (n<2) return 0;  
     int max=Integer.MIN_VALUE, min=Integer.MAX_VALUE;  
     for (int x: nums) {  
       max=Math.max(max,x);  
       min=Math.min(min,x);  
     }  
     int gap=(max-min)/(n-1);  
     if (gap*(n-1)<max-min) gap++;  
     if (gap==0) return 0;  
     int[] minBracket=new int[n];  
     int[] maxBracket=new int[n];  
     Arrays.fill(minBracket, Integer.MAX_VALUE);  
     Arrays.fill(maxBracket, Integer.MIN_VALUE);  
     for (int x: nums) {  
       int i=(x-min)/gap;  
       maxBracket[i]=Math.max(maxBracket[i],x);  
       minBracket[i]=Math.min(minBracket[i],x);  
     }  
     int res=0;  
     int lo=maxBracket[0];//bracket[0] is not blank, at least min will be there  
     for (int i=1; i<n; i++) {  
       if (maxBracket[i]!=Integer.MIN_VALUE) {  
         res=Math.max(res,minBracket[i]-lo);  
         lo=maxBracket[i];  
       }  
     }  
     return res;  
   }  
 }