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 ==0OR
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
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)
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(N3). 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(N2). 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 😀
Gas Station | InterviewBit | Solution Explained
June 13, 2022
Reverse integer | InterviewBit | LeetCode | Solution Explained
January 24, 2022