Largest Divisible Subset: LIS Applied to Divisibility

LeetCode 368: Largest Divisible Subset asks you to find the largest subset of distinct positive integers such that for every pair (a, b) in the subset, either a divides b or b divides a. You need to return the actual subset, not just its size. This is a medium-rated problem, but the path to a clean solution runs straight through a pattern you may already know.

The key insight

Divisibility chains have a transitive property that makes sorting extremely useful. If a divides b and b divides c, then a divides c. Once you sort the array, every element is smaller than those that come after it, so divisibility is one-directional: you only ever need to ask whether a smaller element divides a larger one, never the reverse.

After sorting, the problem collapses to this: for each index i, look at every j where j < i. If nums[i] % nums[j] == 0, then nums[i] can extend whatever chain ended at nums[j]. That is exactly the skeleton of the Longest Increasing Subsequence DP, just with nums[i] % nums[j] == 0 as the comparison predicate instead of nums[j] < nums[i].

The approach

Sort the input. Then for each index i, scan every j where j < i. When nums[i] % nums[j] == 0, you can extend the chain that ended at j. Track dp[i] as the length of the largest divisible subset ending at index i, and keep a parent[i] pointer so you can reconstruct the actual subset at the end.

The recurrence is:

dp[i] = max(dp[j] + 1) for all j < i where nums[i] % nums[j] == 0

Base case: every element is a valid subset of size 1, so dp[i] = 1 initially.

After filling the table, walk back from the index with the highest dp value, following parent pointers, to reconstruct the subset.

The solution

def largestDivisibleSubset(nums):
    nums.sort()
    n = len(nums)
    dp = [1] * n
    parent = [-1] * n
    best_len, best_idx = 1, 0
    for i in range(1, n):
        for j in range(i):
            if nums[i] % nums[j] == 0 and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
                parent[i] = j
        if dp[i] > best_len:
            best_len = dp[i]
            best_idx = i
    result = []
    idx = best_idx
    while idx != -1:
        result.append(nums[idx])
        idx = parent[idx]
    return result[::-1]

Reconstruction via parent pointers

Once the DP table is complete, best_idx holds the index of the last element in the longest chain. Following parent[best_idx], then parent[parent[best_idx]], and so on unwinds the chain in reverse order. Appending each element as you go and reversing at the end gives you the subset in sorted order.

Parent pointer tracking adds one extra integer per index, so the space overhead is just O(n). Without it, you would only know the length of the best subset, not which elements belong to it.

Complexity

The nested loop over all pairs (j, i) dominates. For the constraints LeetCode gives for this problem (n up to 2000), O(n²) is well within the time limit.

Building blocks

This problem is the LIS skeleton with a divisibility predicate swapped in. The structure is:

1. Sort by some key so the comparison becomes one-directional.
2. For each element, scan all predecessors and find the best one to extend.
3. Track parent pointers so you can reconstruct the actual sequence, not just its length.

You see this exact pattern in two closely related problems. In Longest Increasing Subsequence, the predicate is nums[j] < nums[i]. In Russian Doll Envelopes, the sort is two-dimensional and the predicate checks both width and height. The divisibility check here is a third flavour of the same idea.

The transitive property is what makes the approach valid in all three cases. With LIS, transitivity is obvious: if a < b < c, picking a then c is fine. With divisibility, it holds because divisibility is transitive. That means once you sort and check only adjacent-in-chain pairs, you are guaranteed not to miss any valid extension.

Edge cases

• Single element. dp[0] = 1, parent[0] = -1. The reconstruction immediately terminates, returning [nums[0]]. Always valid.
• All primes. No prime divides another prime, but 1 divides everything. If 1 is in the input, the best subset is [1, any_prime], length 2. If 1 is absent, every element is an isolated chain of length 1.
• Duplicates. The problem guarantees distinct positive integers, so you do not need to handle equal elements. The % 0 edge case never arises because all values are positive.

From understanding to recall

Two separate insights need to be active at the same time when you sit down to code this problem.

The first: sorting lets you check divisibility in one direction only. Without that step, you would have to check both a % b and b % a for every pair, and the DP recurrence becomes much harder to define cleanly.

The second: divisibility is transitive, so you only need to track chain membership with a parent pointer, not every pair relationship. The parent at index j already encodes the full chain behind it.

If you have drilled LIS, the code here almost writes itself once you substitute the predicate. If you have not, LIS is the place to start before coming back to this problem.

Related posts

• Longest Increasing Subsequence - the identical DP skeleton with a different predicate
• Russian Doll Envelopes - sort + LIS applied to 2D ordering
• Coin Change - another DP problem with optimal substructure