#368

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Largest Divisible Subset

Find the largest subset of distinct positive integers where every pair satisfies divisibility using state transition dynamic programming.

array math dynamic programming sorting

Problem Statement

Given a set of distinct positive integers nums, identify the largest subset such that for every pair (a, b) in this subset, either a divides b or b divides a. If multiple valid subsets exist, any can be returned.

You are given examples like nums = [1,2,3] where [1,2] is a valid output and nums = [1,2,4,8] where [1,2,4,8] is a valid output. Your task is to implement an efficient algorithm that constructs this largest divisible subset while handling arrays up to length 1000 with unique positive integers.

Examples

Example 1

Input: nums = [1,2,3]

Output: [1,2]

[1,3] is also accepted.

Example 2

Input: nums = [1,2,4,8]

Output: [1,2,4,8]

Example details omitted.

Constraints

1 <= nums.length <= 1000
1 <= nums[i] <= 2 * 109
All the integers in nums are unique.

Solution Approach

Sort and Initialize DP Arrays

Start by sorting the array to ensure that larger numbers are always divisible by smaller ones where possible. Create two arrays: dp[i] to store the size of the largest divisible subset ending at i, and prev[i] to track the previous index in that subset.

Build Subsets Using State Transitions

For each element nums[i], iterate through all previous elements nums[j] where j < i and nums[i] % nums[j] == 0. Update dp[i] = max(dp[i], dp[j] + 1) and set prev[i] = j if a larger subset is found. This captures the state transition dynamic programming pattern for divisible subsets.

Reconstruct the Largest Subset

After populating dp and prev arrays, identify the index of the maximum dp value. Trace back through prev to reconstruct the largest divisible subset. Return the reconstructed subset, which satisfies all divisibility conditions.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n^2) due to the nested iteration for each element to check divisibility against prior elements. Space complexity is O(n) for the dp and prev arrays storing subset lengths and backtracking information.

What Interviewers Usually Probe

Asks about efficient subset building beyond brute force.
Wants you to recognize the dynamic programming state transition pattern.
May probe alternative reconstruction methods and edge cases.

Common Pitfalls or Variants

Common pitfalls

Forgetting to sort nums can break the divisibility chain.
Incorrectly updating dp without checking all previous divisible elements.
Failing to reconstruct the subset using prev pointers after computing dp.

Follow-up variants

Return all largest divisible subsets if multiple exist.
Handle negative integers or zero with adjusted divisibility rules.
Optimize for space using only a single array with backtracking reconstruction.

FAQ

What is the main pattern used in Largest Divisible Subset?

The problem uses state transition dynamic programming to build up subsets based on previous valid divisible elements.

Do I need to sort the array first?

Yes, sorting ensures that every element considered for extension can only divide or be divided by smaller previous elements, simplifying DP transitions.

Can multiple correct outputs exist?

Yes, if there are multiple largest subsets satisfying divisibility, any one of them can be returned.

What is the time complexity of this approach?

The time complexity is O(n^2) because for each element, you may need to check all prior elements for divisibility.

How does GhostInterview handle subset reconstruction?

GhostInterview guides through tracing the prev array from the maximum dp index to reconstruct the largest divisible subset accurately.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

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 ans

Continue Practicing

#1363 largest multiple of three #354 russian doll envelopes #435 non overlapping intervals