# 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
^{3}). 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
^{2}). 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 😀

### Recommended Posts

##### Gas Station | InterviewBit | Solution Explained

June 13, 2022

##### Reverse integer | InterviewBit | LeetCode | Solution Explained

January 24, 2022