I solved it using radix sort


  • 19
    J

    Since linear time and space is required and all nums are non-negative, radix sort seems to be fit.
    Here is the implementation.

    Any better ideas?

    class Solution:
        # @param num, a list of integer
        # @return an integer
        def maximumGap(self, num):
            if len(num) < 2:
                return 0
            num = self.radixSort(num)
            res = 0
            for i in range(1, len(num)):
                res = max(num[i] - num[i - 1], res)
            return res
        
        def radixSort(self, num):
            for i in range(31):
                onebucket = []
                zerobucket = []
                needle = 1 << i
                for j in range(len(num)):
                    if num[j] & needle != 0:
                        onebucket.append(num[j])
                    else:
                        zerobucket.append(num[j])
                num = []
                num += zerobucket
                num += onebucket
            return num

  • 0
    J

    And C++ code for reference:

    class Solution {
    public:
        int maximumGap(vector<int> &num) {
            if (num.size() < 2) return 0;
            int imax = num[0];
            for (int x : num) {
                if (x > imax) imax = x;
            }
            // LSD (least significant digit) radix sort
            int base = 10;
            vector<list<int>> buckets(base);
            vector<int> numbers = num;
            for (long long i = 1; i <= imax; i *= base) {
                // distribute numbers
                for (int x : numbers) {
                    int index = x / i % base;
                    buckets[index].push_back(x);
                }
                // put back numbers
                for (int j = 0, k = 0; j < buckets.size(); j++) {
                    for (int x : buckets[j]) numbers[k++] = x;
                    buckets[j].clear();
                }
            }
            int result = 0;
            for (int i = 1; i < numbers.size(); i++) {
                int gap = numbers[i] - numbers[i-1];
                if (gap > result) result = gap;
            }
            return result;
        }
    };

  • 0

    nice solution where base = 2


  • 0

    My Radix Sort Solution with base = 10
    detailed descriptions on my blog

    class Solution:
    # @param num, a list of integer
    # @return an integer
    def maximumGap(self, num):
    	if len(num) < 2:
    		return 0
    	strNum = []
    	maxSize = 1
    	# convert num to string list, work out max size of num
    	for e in num:
    		eStr = str(e)[::-1] # reversed string
    		strNum.append(eStr)
    		maxSize = max(maxSize, len(eStr))
    	# radix sort
    	for x in range(maxSize):
    		buckets = [[] for y in range(10)]
    		for e in strNum:
    			if len(e) <= x:
    				buckets[0].append(e)
    			else:
    				buckets[int(e[x])].append(e)
    		strNum = []
    		for y in range(10):
    			strNum.extend(buckets[y])
    	num = [int(x[::-1]) for x in strNum]
    	maxGap = 0
    	for x in range(len(num) - 1):
    		maxGap = max(maxGap, num[x + 1] - num[x])
    	return maxGap
    

  • 7
    L

    My JAVA version:

    public class Solution {
        public int maximumGap(int[] num) {
            if(num == null || num.length < 2) {
                return 0;
            }
            int length = num.length;
            List<Integer> sorted = new ArrayList<Integer>(length);
            for(int i : num) {
                sorted.add(i);
            }
    
            //2 buckets
            List<Integer> bucket0 = new ArrayList<Integer>();
            List<Integer> bucket1 = new ArrayList<Integer>();
    
            int mask = 1;
            //31 iterations
            while(mask > 0) {
                for(int i = 0; i < length; i ++) {
                int n = sorted.get(i);
                if((n & mask) == 0) {
                     bucket0.add(n);
                } else {
                     bucket1.add(n);
                }
            }
                sorted.clear();
                sorted.addAll(bucket0);
                sorted.addAll(bucket1);
                bucket0.clear();
                bucket1.clear();
                mask <<= 1;
            }
    
            int maxDiff = 0;
            for(int i = 1; i < length; i ++) {
                int n = sorted.get(i) - sorted.get(i - 1);
                if(n > maxDiff) maxDiff = n;
            }
            return maxDiff;
        }
    }

  • 0
    S

    My readable Java solution with base = 2:

    public class Solution {
        
        List<Integer> zeros = new ArrayList<>();
        List<Integer> ones = new ArrayList<>();
        
        public int maximumGap(int[] num) {
            if (num == null || num.length < 2) {
                return 0;
            }
            for (int b = 0; b < 31; b++) {
                putIntoBuckets(num, b);
                putFromBuckets(num);
            }
            return maximumGapFromSorted(num);
        }
        
        public void putIntoBuckets(int[] num, int b) {
            zeros.clear();
            ones.clear();
            
            int mask = 1 << b;
            for (int i : num) {
                if ((i & mask) == 0) {
                    zeros.add(i);
                } else {
                    ones.add(i);
                }
            }
        }
                
        public void putFromBuckets(int[] num) {
            int i = 0;
            for (int z : zeros) {
                num[i++] = z;
            }
            for (int o : ones) {
                num[i++] = o;
            }
        }
        
        public int maximumGapFromSorted(int[] num) {
            int maxGap = 0;
            for (int i = 0; i < num.length - 1; i++) {
                maxGap = Math.max(maxGap, num[i+1] - num[i]);
            }
            return maxGap;
        }
      
    }

  • 1
    Z

    Ok, so you have 31 bits. How many different numbers can you have on 31 bits? 2^31. How many iterations does you algorithm require? Number of numbers * number of bits, i.e. 2^31 * 31. If n=2^31 then 31 is logn. The time complexity of your algorithm is O(n*logn) and it's far from linear.


  • 0
    Z

    Ok, so you have 31 bits. How many different numbers can you have on 31 bits? 2^31. How many iterations does you algorithm require? Number of numbers * number of bits, i.e. 2^31 * 31. If n=2^31 then 31 is logn. The time complexity of your algorithm is O(n*logn) and it's far from linear. This is not better than calling Arrays.sort()!


  • 0
    I

    The fixed number of bits/passes (e.g. int size measured in bits) is part of the constant in O(n)


  • 20
    M

    Another (tiny) C++ radix-sort solution,

    int maximumGap(std::vector<int> &num) {
    	for(unsigned bit = 0; bit < 31; bit++)
    	std::stable_partition(num.begin(), num.end(), [bit](int a){
    		return !(a & (1 << bit));
    	});
    	int difference = 0;
    	for(std::size_t i = 1; i < num.size(); i++) {
    		difference = std::max(difference, num[i] - num[i-1]);
    	}
    	return difference;
    }
    

    STL is super nice for this sort of thing


  • 0
    S

    I agree with zsolt. The way you level up bits is O(log n).


  • 0
    C

    @zsolt is right. radix sort is efficient when the number of digits of the elements is constant, and the number of elements are sufficiently large. For a list of distinct elements, the running time is O(n*logn)


  • 0
    L

    It seems to me that the algorithm can be further optimized by limitting the number of rounds of the radix sorting, up to the number of bits of the max element, instead of the length of bits of Integer.

    The complexity of the radix sort is indeed O(N). When it comes to the practice, the number of constant for O(N) matters.

    For instance, given an input {1, 2, 3}, the above algorithms would all enumerate the list 32 times. But as one can observe from the list, we only need 2 rounds of radix sort, since after that, all elements would be attributed to the bucket zero.

    So here is a sort of optimised radix sorting algorithm.

    public void radixSort(int [] num){
    
    	int max = Integer.MIN_VALUE;
    	// Initialise the memory buffer for the radix sorting.
    	ArrayList<Integer> sortBuffer = new ArrayList<Integer>();
    	for(int n : num){
    		max = n > max ? n : max;
    		sortBuffer.add(n);
    	}
    	
    	int mask = 2;
    	int bit_num = 1; // the number of bits for the max value.
    	while(max / mask > 0){
    		++bit_num;
    		mask <<= 1;
    	}
    	
    	ArrayList<Integer> bucket0 = new ArrayList<Integer>();
    	ArrayList<Integer> bucket1 = new ArrayList<Integer>();
    	
    	mask = 1;
    	// Do the radix sort up to the "bit_num" round, instead of 32.
    	while(bit_num-- > 0){
    		
    		for(Integer n : sortBuffer){
    			boolean eb = ((int)n & mask) == 0 ? 
    				bucket0.add(n) : bucket1.add(n);
    		}
    		mask <<= 1;
    			
    		sortBuffer.clear();
    		sortBuffer.addAll(bucket0);
    		sortBuffer.addAll(bucket1);
    		
    		bucket0.clear();
    		bucket1.clear();
    		
    	}
    	
    	// Copy the sorted list to the original list.
    	for(int i=0; i<num.length; ++i){
    		num[i] = sortBuffer.get(i);
    	}
    }
    
    
    public int maximumGap(int[] num) {
    	if(num.length < 2){
    		return 0;
    	}
    	
    	this.radixSort(num);
    	
    	int max_gap = Integer.MIN_VALUE;
    	for(int i=1; i<num.length; i++){
    		int gap = num[i]-num[i-1];
    		max_gap = gap > max_gap ? gap : max_gap; 
    	}
    	return max_gap;
    }
    

  • 0
    L

    Since the problem itself explicitly states that the elements have at most 31 bits, I think we should treat 31 as constant other than logn. Of course it can be optimized for the practice.


  • 0
    S

    Java radix-sort solution with base 10:

    public class Solution {
        
        private List<Integer> radixSort(int[] arr) {
            List<List<Integer>> radix = new ArrayList<>();
            for (int i = 0; i < 10; i++) radix.add(new LinkedList<Integer>());
            for (int n : arr) radix.get(n % 10).add(n);
            for (int i = 1; i < 10; i++) {
                List<List<Integer>> newRadix = new ArrayList<>();
                for (int j = 0; j < 10; j++) newRadix.add(new LinkedList<Integer>());
                for (List<Integer> qr : radix) {
                    for (int n : qr) {
                        int tmp = n;
                        for (int k = i; k > 0; k--) n /= 10;
                        newRadix.get(n % 10).add(tmp);
                    }
                }
                radix = newRadix;
            }
            return radix.get(0);
        }
    
        public int maximumGap(int[] num) {
            if (num.length < 2) return 0;
            int prev = Integer.MIN_VALUE, maxGap = Integer.MIN_VALUE;
            for (int n : radixSort(num)) {
                maxGap = Math.max(n - prev, maxGap);
                prev = n;
            }
            return maxGap;
        }
        
    }

  • 0
    C

    @zsolt I think this solution is right, as it cost at most O(n*logn) and the logn is bounded to 32, so it sums upto O(32n) = O(n)


  • 0
    C

    the key idea is that you can not find more than 2^31 distinct numbers with 31 bits


  • 0
    C

    Arrays.sort is not correct because usually it is an implementation of quick sort and quick sort only has a average time complexity of O(n logn), it can be as slow as O(n^2).

    the real time complexity of radix sort is O(n log m) where m is the distinct numbers count and m < 2^31 (n can be larger than 2^31)


  • 0
    R

    The integer is indeed 31 bits but in its binary form.
    The radix sort normally iterates over decimal numbers rather than binary bits so the range is 10 instead of 31. The reason is simple, 2^31-1 = 2147483647 has at most 10 digits. 10 iteration is sufficient for this problem in decimal space. Reducing the number of buckets does not reduce the size of the problem due to the size of the inner loop and the performance is thus worse than traditional radix sort and worse than nlogn comparison sort.

    Here are some details:

    This solution has O(31n) complexity, in order to make the performance better than O(nlogn), 31 must be less than logn, right?

    Then how large the n should be? it is 2 to the power of 31 which is 2147483648, then the num list must be longer than that to make this solution faster than std nlogn sorting algorithm.

    In another words, the best case performance is equal to nlogn std sorting algorithm and worse than nlogn as long as the number of elements is less than 2147483648;

    @chasezhang Your are right it is bounded to 32 and it is O(n) but it is still worse than nlogn algorithms regarding this particular problem due to the input range cannot reach the point this solution starts to win.


  • 0
    M

    I like your solution !


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.