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.

New LeetCode problem. The algorithm is referred from the application of Pigeonhole principle. It is beautiful, smart and very easy to understand.

Ah, that's why I love math (even though I am not good at it): it always solves the hard problem by the simplest principles.

Update: 2015 - 03 - 04
Briefly, the maximum gap between two successive integers must lie between the maximum number in one bucket and the minimum number in the next bucket.

public class MaxGap {
    public int maximumGap(int[] nums) {
         if (nums == null || nums.length < 2)
             return 0;
         if (nums.length == 2) {
             return Math.abs(nums[0] - nums[1]);
         }
         int max = nums[0];
         int min = nums[0];
         int len = nums.length;
         for (int i = 0; i < len; i++) {
             max = Math.max(nums[i], max);
             min = Math.min(nums[i], min);
         }
         int[] max_buckets = new int[len - 1];
         int[] min_buckets = new int[len - 1];
         for (int i = 0; i < len - 1; i++) {
             max_buckets[i] = -1;
             min_buckets[i] = Integer.MAX_VALUE;
         }
         double interval = ((double)max - (double)min) / (double)(len - 1);
         for (int i = 0; i < len; i++) {
             if (nums[i] == max) {
                 max_buckets[len - 2] = nums[i];
                 continue;
             }
             int b = (int)((nums[i] - min) / interval);
             max_buckets[b] = Math.max(max_buckets[b], nums[i]);
             min_buckets[b] = Math.min(min_buckets[b], nums[i]);
         } 
         
         if (min_buckets[len - 2] == Integer.MAX_VALUE) {
             min_buckets[len - 2] = max;
         }
         int max_gap = 0;
         int index1 = len - 2, index2 = len - 3;
         while (index2 >= 0 && index1 > index2) {
             while (index2 >= 0 && max_buckets[index2] == -1) {
                 index2--;
             }
             while (index1 > index2 && min_buckets[index1] == Integer.MAX_VALUE) {
                 index1--;
             }
             max_gap = Math.max(max_gap, min_buckets[index1] - max_buckets[index2]);
             index2--;
             index1--;
         }
         return max_gap;
     }
}