292 ms Python solution


  • 2
    G

    The idea is to put the (sorted) numbers into buckets one by one and make sure each number is divisible by one number in previous buckets. So the index of the bucket is the max size of a set.

    Num      1, 2, 3, 4, 6, 8, 9, 12, 24, 36
    
    bucket   1  2  3  4  5 
    -----------------------
             1  2  4  8 24
                3  6 12 36
                   9
    

    After doing this, all I need to do is find a path between the first bucket and the last. We can do this using DFS but I choose to put a tuple (d, p) into buckets instead of a number where f is the divider and p is the number.

    class Solution(object):
        def largestDivisibleSubset(self, nums):
            """
            :type nums: List[int]
            :rtype: List[int]
            """
            nums = sorted(nums)
            buckets = [None, []]
            if len(nums) < 2:
                return nums
            max_len = 0
            for n in nums:
                atemp = max_len + 1
                placed = False
                while atemp > 0 and not placed:
                    if atemp == 1:
                        buckets[1].append((None, n))
                        max_len = max(max_len, atemp)
                        placed = True
                    else:
                        for _, p in buckets[atemp-1]:
                            if n % p == 0:
                                while len(buckets) - 1 < atemp:
                                    buckets.append([])
                                buckets[atemp].append((p, n))
                                max_len = max(max_len, atemp)
                                placed = True
                                break
                    atemp -= 1
            ans = [buckets[-1][0][1]]
            target = buckets[-1][0][0]
            for i in xrange(max_len-1, 0, -1):
                for d, p in buckets[i]:
                    if p == target:
                        ans.insert(0, p)
                        target = d
                        break
            return ans
    

Log in to reply
 

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