LeetCode 368: Largest Divisible Subset

Problem Restatement

We are given a set of distinct positive integers nums.

Return the largest subset answer such that for every pair of numbers in answer, one number divides the other.

For any pair:

answer[i], answer[j]

at least one of these must be true:

answer[i] % answer[j] == 0

or:

answer[j] % answer[i] == 0

If there are multiple valid largest subsets, return any one of them. The official examples include nums = [1,2,3], where [1,2] or [1,3] is accepted, and nums = [1,2,4,8], where the full array is valid.

Input and Output

Example function shape:

def largestDivisibleSubset(nums: list[int]) -> list[int]:
    ...

Examples

Example 1:

nums = [1, 2, 3]

Valid answers include:

[1, 2]

and:

[1, 3]

Both have length 2.

We cannot take [1, 2, 3] because:

3 % 2 != 0

and:

2 % 3 != 0

So 2 and 3 cannot both be in the same divisible subset.

Example 2:

nums = [1, 2, 4, 8]

The whole list is valid:

[1, 2, 4, 8]

because each larger number is divisible by each smaller number.

First Thought: Try All Subsets

A brute force solution would generate every subset of nums.

For each subset, check whether every pair satisfies the divisibility rule.

There are:

2 ** n

subsets.

This becomes too slow quickly.

We need to use structure.

Key Insight

Sort the numbers.

After sorting, if we build a chain:

a1 <= a2 <= a3 <= ...

and every next number is divisible by the previous number:

a2 % a1 == 0
a3 % a2 == 0

then every later number is divisible by every earlier number.

Why?

Divisibility is transitive.

If:

a2 % a1 == 0

and:

a3 % a2 == 0

then a3 is also divisible by a1.

So after sorting, the problem becomes similar to Longest Increasing Subsequence, except the transition condition is divisibility.

We compute the longest divisible chain ending at each index.

Algorithm

Sort nums.

Create two arrays:

Initialize:

dp[i] = 1
parent[i] = -1

because every number alone is a valid subset.

For each i, check every j < i.

If:

nums[i] % nums[j] == 0

then nums[i] can extend the subset ending at nums[j].

Update:

dp[i] = dp[j] + 1
parent[i] = j

if this gives a longer subset.

After filling DP:

1. Find the index with the largest dp[i].
2. Follow parent links backward.
3. Reverse the result.

Correctness

After sorting, every candidate subset can be written in non-decreasing order.

For a valid divisible chain ending at nums[i], the previous element must be some nums[j] where j < i and:

nums[i] % nums[j] == 0

The DP checks all such previous indices.

If a subset ending at nums[j] is valid, then appending nums[i] keeps the subset valid because nums[i] is divisible by nums[j], and by transitivity it is also divisible by every earlier element in that chain.

Therefore, dp[i] correctly stores the length of the largest valid subset ending at nums[i].

The parent array records the previous index that produced the best value, so following parent links reconstructs an actual largest subset.

The algorithm chooses the maximum over all ending indices, so it returns a largest divisible subset.

Complexity

Let n = len(nums).

Sorting costs O(n log n), which is dominated by the DP.

Implementation

class Solution:
    def largestDivisibleSubset(self, nums: list[int]) -> list[int]:
        nums.sort()
        n = len(nums)

        dp = [1] * n
        parent = [-1] * n

        best_len = 1
        best_index = 0

        for i in range(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_index = i

        answer = []

        while best_index != -1:
            answer.append(nums[best_index])
            best_index = parent[best_index]

        answer.reverse()
        return answer

Code Explanation

We sort first:

nums.sort()

This lets us only check whether a later, larger number is divisible by an earlier, smaller number.

Each number starts as a subset of length 1:

dp = [1] * n

The parent array starts with -1:

parent = [-1] * n

A value of -1 means this number starts the chain.

For each pair j < i, we test divisibility:

if nums[i] % nums[j] == 0:

If extending from j creates a longer chain, update both arrays:

dp[i] = dp[j] + 1
parent[i] = j

We also track the best ending index:

if dp[i] > best_len:
    best_len = dp[i]
    best_index = i

Finally, reconstruct by following parent links:

while best_index != -1:
    answer.append(nums[best_index])
    best_index = parent[best_index]

This builds the answer backward, so we reverse it:

answer.reverse()

Testing

def is_valid_subset(nums, subset):
    nums_count = {x: nums.count(x) for x in nums}

    for x in subset:
        if x not in nums_count or nums_count[x] == 0:
            return False
        nums_count[x] -= 1

    for i in range(len(subset)):
        for j in range(i + 1, len(subset)):
            a = subset[i]
            b = subset[j]
            if a % b != 0 and b % a != 0:
                return False

    return True

def run_tests():
    s = Solution()

    ans = s.largestDivisibleSubset([1, 2, 3])
    assert len(ans) == 2
    assert is_valid_subset([1, 2, 3], ans)

    ans = s.largestDivisibleSubset([1, 2, 4, 8])
    assert ans == [1, 2, 4, 8]

    ans = s.largestDivisibleSubset([4, 8, 10, 240])
    assert len(ans) == 3
    assert is_valid_subset([4, 8, 10, 240], ans)

    ans = s.largestDivisibleSubset([3])
    assert ans == [3]

    ans = s.largestDivisibleSubset([2, 3, 4, 9, 8])
    assert len(ans) == 3
    assert is_valid_subset([2, 3, 4, 9, 8], ans)

    print("all tests passed")

run_tests()

Test meaning: