164.md

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.

Credits:
Special thanks to @porker2008 for adding this problem and creating all test cases.

my thoughts:

1. brutal force failed.
TLE

2. re-learn radix sort.

my solution:

**********TLE
class Solution:
    def maximumGap(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums = set(nums)
        l = len(nums)
        if l < 2:
            return 0
        if l == 2:
            return abs(list(nums)[0] - list(nums)[1])
        res = 0
        count = 0
        i, j = 0, 0
        while j < l:
            i += 1
            if j > 0:
                count += 1
            if i in nums:
                j += 1
                res = max(res, count)
                count = 0
        return res
		
		
**********
class Solution:
    def maximumGap(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums = set(nums)
        l = len(nums)
        if l < 2:
            return 0
        if l == 2:
            return abs(list(nums)[0] - list(nums)[1])
        maxNum = max(nums)
        nums = list(nums)
        i = 0
        while maxNum>>i > 0:
            z, o = [], []
            for n in nums:
                if n & 1<<i:
                    o.append(n)
                else:
                    z.append(n)
            nums = z + o
            i += 1
        res = 0
        for i in range(l-1):
            res = max(res, nums[i+1] - nums[i])
            
        
        return res

my comments:

from other ppl's solution:

1. bucket sort:
I made some improvements of the original version to make it simpler.

1. if min==max, we can return 0 directly.
2. the length of bucketMin and bucketMax is n rather than n-1. So max can be put in bucket.
3. to check if bucket is empty, check if(bucketMin[i]!=Integer.MAX_VALUE) is ok
4. do not need maxGap, gap is enough.


    public int maximumGap(int[] nums) {
            if(nums==null || nums.length<2)
                return 0;
                
            int min=nums[0];
            int max=nums[0];
            for(int n: nums){
                min=Math.min(min, n);
                max=Math.max(max, n);
            }
            if(min==max)
                return 0;
                
            int n=nums.length;
            
            int gap = (int)Math.ceil((double)(max-min)/(n-1));
            int bucketMin[] = new int[n];
            int bucketMax[] = new int[n];
            Arrays.fill(bucketMin, Integer.MAX_VALUE);
            Arrays.fill(bucketMax, Integer.MIN_VALUE);
            
            for(int num: nums){
                int i=(num-min)/gap;
                bucketMin[i] = Math.min(bucketMin[i], num);
                bucketMax[i] = Math.max(bucketMax[i], num);
            }
            
        
            for(int i=0;i<bucketMin.length;++i){
                if(bucketMin[i]!=Integer.MAX_VALUE){
                    gap = Math.max(gap, bucketMin[i]-min);
                    min = bucketMax[i];
                }
            }
            
            return gap;
        }