Problem 368

(Last updated: )

Question statement:

Given a set of distinct positive integers nums, return the largest subset answer such that every pair (answer[i], answer[j]) of elements in this subset satisfies:
answer[i] % answer[j] == 0, or
answer[j] % answer[i] == 0

Solution

Main idea:

Certainly the second condition is a red-herring. We can start by sorting the array, so we only have to check for the first condition. Next up, we do a 1-d dp approach, where dp[i] stores the longest valid subset that includes and terminates at nums[i]. Then at step i+1, we simply scan backwards from i, and if nums[j] divides nums[i], then we have a potential candidate for dp[i], namely dp[j] + [nums[i]]. We also keep track of the longest potential candidate, and if this one is better than our current best, we replace the current best with this one. Finally, after the backward check is finished, we check if the current best candidate is better than the best candidate we have seen so far, and updating the best candidate as necessary. Finally, we append the current_candidate to the dp array, and move on to i+2. Finally, once we i has run through the entire array nums, we simply return the best candidate recorded across all i’s as our ans.

Note: This strategy is still suboptimal since we do a lot of unnecessary checking when we walk backwards from i. In a sense, once we checked nums[j]=dp[j][-1], we can essentially ignore checking all other entries stored in dp[j]. I thought about implementing this, but the code started to look a lot more complicated and a bit convoluted. So I opted for cleaner code, compromising on the run time a bit. If I end up writing a more optimized solution, I will update this blog post with it.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
    if(len(nums) == 1):
        return [nums[0]]
    if(len(nums) == 0):
        return []  
    nums = sorted(nums)
    dp_substr = [[nums[0]]] 
    ans = []
    for i in range(1, len(nums)):
        cur_candidate = [nums[i]]
        for j in range(i-1, -1, -1):
            if(nums[i] % nums[j] == 0):
                temp = dp_substr[j] + [nums[i]]
                if(len(temp) > len(cur_candidate)):
                    cur_candidate = temp
        if(len(cur_candidate) >= len(ans)):
            ans = cur_candidate
        dp_substr.append(cur_candidate)
    return ans

Comments:

Time complexity: O($n^2$)

At the time of submission, the above solution passes leetcode submission cases in 210ms, beats 83.32% of users. It uses 16.96MB of memory, beating 65.23% of users.