Python solution with detailed explanation


  • 0
    G

    Solution

    Maximum Gap https://leetcode.com/problems/maximum-gap/?tab=Description

    Radix Sort Solution

    1. The first algorithm is to sort the numbers using radix-sort. We use the algorithm for sorting constant width strings moving from least significant to most significant digit. For example, sorting 334, 146, 192:
    • First sort by the units digits (4, 6, 2): 192, 334, 146
    • Sort by tens digit (9,3,4): 334, 146, 192
    • Sort by hundreds digit (3,1,1): 146, 192, 334
      2: How do we determine width of these integers? width = len(str(2^31-1))-1
      3: https://www.youtube.com/watch?v=xhr26ia4k38
    from collections import defaultdict
    class Solution(object):
        def radix_sort(self, nums, width):
            q = 1
            for w in range(width):
                q = q*10 if w > 0 else 1
                num_dict = defaultdict(list)
                for x in nums:
                    digit = (x // q) % 10
                    num_dict[digit].append(x)
                i = 0
                for k in range(10):
                    for x in num_dict[k]:
                        nums[i], i = x, i+1
            return
        
        def maximumGap(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            width = len(str(2**31-1))-1
            self.radix_sort(nums, width)        
            max_gap = 0
            for i in range(1, len(nums)):
                max_gap = max(nums[i] - nums[i-1], max_gap)
            return max_gap
    

    Radix Sort (2) Solution

    • Alternative implementation for Radix Sort as given by Sedgewick.
    class Solution(object):
        def radix_sort(self, nums, width):
            q = 1
            for w in range(width):
                q = q*10 if w > 0 else 1
                radix = [0]*11
                # Get the frequency of each alphabet
                for x in nums:
                    digit = (x // q) % 10
                    radix[digit+1] = radix[digit+1] + 1
                # Build the cumulative array. This array tells us
                # the starting position for every character in the temp array.
                for i in range(1,11):
                    radix[i] = radix[i-1] + radix[i]
                temp = [None]*len(nums)
                for x in nums:
                    digit = (x // q) % 10
                    temp[radix[digit]] = x
                    radix[digit] = radix[digit] + 1
                for i in range(len(temp)):
                    nums[i] = temp[i]
            return    
    
        def maximumGap(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            width = len(str(2**31-1))-1
            self.radix_sort(nums, width)        
            max_gap = 0
            for i in range(1, len(nums)):
                max_gap = max(nums[i] - nums[i-1], max_gap)
            return max_gap
    

    Bucket Sort
    The bucket sort algorithm is explained with comments. https://discuss.leetcode.com/topic/5999/bucket-sort-java-solution-with-explanation-o-n-time-and-space/2

    class Solution(object):
        def maximumGap(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            N = len(nums)
            if N < 2:
                return 0
            min_n, max_n = min(nums), max(nums)
            gap = int(ceil((max_n-min_n)/float(N-1)))
            buckets = [[None, None] for _ in range(N-1)]
            for x in nums:
                if x == max_n:
                    continue
                slot = int((x-min_n)/gap)
                buckets[slot][0] = min(buckets[slot][0], x) if buckets[slot][0] else x
                buckets[slot][1] = max(buckets[slot][1], x) if buckets[slot][1] else x
            max_gap, prev_max = gap, buckets[0][1]
            for b in buckets:
                if b[0] == None and b[1] == None:
                    continue
                else:
                    max_gap = max(max_gap, b[0]-prev_max)
                    prev_max = b[1]
            if prev_max:
                max_gap = max(max_gap, max_n-prev_max)
            return max_gap
    

Log in to reply
 

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