Maximum Gap

Maximum Gap

26%

Accepted

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Return 0 if the array contains less than 2 elements.

Have you met this question in a real interview? 

Yes

Example

Given [1, 9, 2, 5], the sorted form of it is [1, 2, 5, 9], the maximum gap is between 5 and 9 = 4.

Note

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

Challenge

Sort is easy but will cost O(nlogn) time. Try to solve it in linear time and space.

class Solution {
    /**
     * @param nums: an array of integers
     * @return: the maximum difference
     */
    public int maximumGap(int[] nums) {
               if(nums == null || nums.length <= 1) return 0;
        int minNum = Integer.MAX_VALUE, maxNum = Integer.MIN_VALUE;
        for(int i = 0; i < nums.length; i++){
            minNum = Math.min(minNum, nums[i]);
            maxNum = Math.max(maxNum, nums[i]);
        }
       
        int gap = (int)Math.ceil((double)(maxNum - minNum) / (nums.length - 1));
        if(gap == 0) return 0;
        int n =(int) Math.ceil((double) (maxNum - minNum) / gap);
        int[] minBucket = new int[nums.length];
        int[] maxBucket = new int[nums.length];
        Arrays.fill(minBucket, Integer.MAX_VALUE);
        Arrays.fill(maxBucket, Integer.MIN_VALUE);
        for(int i = 0; i < nums.length; i++){
            int idx = (nums[i] - minNum) / gap;
            minBucket[idx] = Math.min(minBucket[idx], nums[i]);
            maxBucket[idx] = Math.max(maxBucket[idx], nums[i]);
        }    
        int maxGap = 0, previous = minNum;
        for(int i = 0; i < n; i++){
            if(minBucket[i] == Integer.MAX_VALUE && maxBucket[i] == Integer.MIN_VALUE) continue;
            maxGap = Math.max(maxGap, minBucket[i] - previous);
            previous = maxBucket[i];
           
        }
       
        return Math.max(maxGap, maxNum - previous);
    }
}