Largest Divisible Subset | LeetCode | GeeksforGeeks | DP Solution Explained

368. Largest Divisible Subset. I explain the Dynamic Programming approach using simple examples and visuals, along with a mathematical optimization (as bonus).

0. Largest Divisible Subset: Problem Discussion

0.0. IO Format

• given: nums – a set of distinct integers
• goal: ans – a subset following the condition
• condition: all pairs of elements (x, y) in a subset follow x % y ==0 OR y % x == 0

in other words, one is the factor of the other number, for a given pair of numbers in a given subset.

1. Largest Divisible Subset: Observations & Logic

1.0. Intuitions

As I suggest, we start form a couple of basic cases.

The blue is the input nums array and the green is the answer/possible answers.

The first thing we notice is that if we somehow have the answers computed for 1 2 3 4, then calculating the answers for 1 2 3 4 5 and 1 2 3 4 5 6 becomes a lot easier – we know the answer for a part of the array already!

1.1. Solidifying Intuitions

Let’s start again from the very small case:

For the number 1, we can store the information for 1 in yellow color.

When we add the number 2 to the list, we can connect 2 with 1 as such:

Now, the answer for 1 (in yellow) remains as is, but the answer for 2 becomes 1, 2 since we linked 2 with 1. In fact, 1, 2 now becomes our answer!

In the case of 1, 3, we can’t add 3 to the link of 2 (the 1, 2 chain). What now? We can still connect 3 to 1, since that follows the conditions.

Similarly, we see:

1.2. A Sneaky Issue

Note how this assumes sorting. Wait what? Why? Let’s see what happens if we don’t sort the array.

As we iterate, we keep on linking the current element with the previous elements. Note how till 15, 1, 3, we don’t really bother. Life is fine.

But, when it comes to 9, why do we start again? That’s because 9 can’t link to any of the previous elements. It can’t link to 15 or 15, 1 or 15, 1, 3 – due to 15. That in a way, blocks the elements 1 and 3 from linking with other elements.

2. Largest Divisible Subset: Implementation (Accepted)

2.0. Code

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        nums.sort()
        dp = [[x] for x in nums]
        
        for i, x in enumerate(nums):
            for j in range(i):
                flag = True
                for y in dp[j]:
                    if not (x % y == 0 or y % x == 0):
                        flag = False
                        break
                if flag:
                    dp[i] = max(dp[i], dp[j] + [x], key=len)
        return max(dp, key=len)

2.1. Complexity Analysis

• Time: O(N³). O(N) for iterating over nums, O(N) to go over the previous DP elements, O(N) to check each of those DP elements.
• Space: O(N²). O(N) for all the answers corresponding to the nums, and O(N) for the size of each list.

3. Largest Divisible Subset: Mathematical Optimization

coming soon 😀

Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.