MediumNo. 0368
Largest Divisible Subset — LeetCode 368 Python Solution
- Pattern
- Sorting
- Topics
- Array, Math, Dynamic Programming, Sorting
- Reading time
- 4 min
- Source
- leetcode.com
The problem
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 If there are multiple solutions, return any of them.
Example
- Input
- nums = [1,2,3]
- Output
- [1,2]
- Explanation
- [1,3] is also accepted.
Python solution
class Solution:
def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
nums.sort()
n = len(nums)
f = [1] * n
k = 0
for i in range(n):
for j in range(i):
if nums[i] % nums[j] == 0:
f[i] = max(f[i], f[j] + 1)
if f[k] < f[i]:
k = i
m = f[k]
i = k
ans = []
while m:
if nums[k] % nums[i] == 0 and f[i] == m:
ans.append(nums[i])
k, m = i, m - 1
i -= 1
return ansComplexity
- Time
- O(n·m) (typical)
- Space · auxiliary
- O(n·m)or optimized
Pattern: Sorting
Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 368. Largest Divisible Subset is filed here because LeetCode tags it Sorting, which is the vocabulary this hub collects.
The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 1363 | Largest Multiple of Three | Hard |
| 1478 | Allocate Mailboxes | Hard |
| 2681 | Power of Heroes | Hard |
| 0313 | Super Ugly Number | Medium |
| 0396 | Rotate Function | Medium |
| 0435 | Non-overlapping Intervals | Medium |
Frequently asked questions
- How hard is LeetCode 368. Largest Divisible Subset?
LeetCode 368. Largest Divisible Subset is rated Medium on LeetCode.
- What topics does LeetCode 368. Largest Divisible Subset cover?
LeetCode 368. Largest Divisible Subset is tagged Array, Math, Dynamic Programming and Sorting on LeetCode.