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.
public class Solution { public int maximumGap(int[] num) { if(num.length<2) return 0; Arrays.sort(num); int max = num[1] - num[0]; for(int i = 2; i< num.length ; i++){ max = Math.max(max,num[i]-num[i-1]); } return max; } }
public class Solution { public int maximumGap(int[] num) { if(num.length<2) return 0; int min = num[0]; int max = num[0]; for (int i:num) { min = Math.min(min, i); max = Math.max(max, i); } int gap = (int)Math.ceil((double)(max - min)/(num.length - 1)); int[] bucketsMIN = new int[num.length - 1]; // store the min value in that bucket int[] bucketsMAX = new int[num.length - 1]; // store the max value in that bucket Arrays.fill(bucketsMIN, Integer.MAX_VALUE); Arrays.fill(bucketsMAX, Integer.MIN_VALUE); for(int i:num){ if (i == min || i == max) continue; int index = (i - min)/gap; bucketsMIN[index] = Math.min(i,bucketsMIN[index]); bucketsMAX[index] = Math.max(i,bucketsMAX[index]); } int maxGap = Integer.MIN_VALUE; int pres = min; for(int i = 0 ; i < num.length -1 ; i++){ if (bucketsMIN[i] == Integer.MAX_VALUE && bucketsMAX[i] == Integer.MIN_VALUE) // empty bucket continue; // min value minus the previous value is the current gap maxGap = Math.max(maxGap,bucketsMIN[i] - pres); pres = bucketsMAX[i]; } maxGap = Math.max(maxGap, max - pres); return maxGap; } }