LeetCode 368 - Largest Divisible Subset

LeetCode Problem 368

Difficulty: 🟡 Medium
Topics: Array, Math, Dynamic Programming, Sorting

Solution

Problem Understanding

The problem gives us an array of distinct positive integers and asks us to find the largest subset where every pair of numbers satisfies a divisibility relationship. For any two elements a and b in the subset, either a % b == 0 or b % a == 0 must hold.

In other words, every pair of values in the chosen subset must be compatible under divisibility. The subset does not need to preserve the original order of the input array, and if multiple valid largest subsets exist, returning any one of them is acceptable.

The input consists of:

• An array nums
• All numbers are positive
• All numbers are unique
• The array length can be as large as 1000
• Individual values can be as large as 2 * 10^9

The constraint on nums.length is especially important. A size of 1000 is large enough that exponential brute-force subset generation becomes infeasible. Since there are 2^n possible subsets, a naive exhaustive search would be impossibly slow.

The uniqueness guarantee simplifies the problem because we never need to worry about duplicate values creating ambiguous chains or repeated divisibility checks.

Several edge cases are important to recognize early:

• A single-element array is always valid because one number trivially satisfies the condition.
• Arrays where no two numbers divide each other should return any single element.
• Arrays containing long divisibility chains such as [1,2,4,8,16] should return the full array.
• Large prime-heavy arrays may produce only very small valid subsets.
• Because all numbers are positive, divisibility behavior remains straightforward and avoids issues involving zero or negative values.

Approaches

Brute Force Approach

The brute-force solution would generate every possible subset of the array and check whether that subset satisfies the divisibility condition.

For each subset, we would compare every pair of elements. If every pair satisfies the rule that one divides the other, the subset is valid. We would then track the largest valid subset found.

This approach is correct because it explicitly checks all possible subsets, guaranteeing that the optimal answer will eventually be discovered.

However, the runtime is prohibitively expensive. An array of size n has 2^n subsets. For each subset, checking all pairs may require O(n^2) work. With n = 1000, this approach is completely infeasible.

Key Insight for an Optimal Solution

The critical observation is that divisibility behaves transitively after sorting.

If we sort the numbers in ascending order, then for a valid divisible subset:

• Smaller numbers appear before larger numbers
• If a divides b and b divides c, then a also divides c

This transforms the problem into something very similar to the Longest Increasing Subsequence problem.

After sorting, we can define:

• dp[i] = length of the largest divisible subset ending at index i
• parent[i] = previous index in the chain, used for reconstruction

For each number nums[i], we look at all previous numbers nums[j] where j < i. If nums[i] % nums[j] == 0, then nums[i] can extend the subset ending at j.

This dynamic programming approach efficiently builds the best chain ending at every position.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n * n^2)	O(n)	Generates all subsets and validates each one
Optimal Dynamic Programming	O(n^2)	O(n)	Sorts the array and builds longest divisible chains

Algorithm Walkthrough

1. Sort the input array in ascending order.

Sorting is essential because divisibility chains naturally grow from smaller numbers to larger numbers. Once sorted, if nums[i] is divisible by nums[j] for j < i, then nums[i] can extend the chain ending at j. 2. Create a dp array.

dp[i] stores the length of the largest divisible subset ending at index i.

Initially, every element can form a subset containing only itself, so all values start as 1. 3. Create a parent array.

parent[i] stores the previous index in the divisible chain ending at i.

This allows reconstruction of the final subset after the dynamic programming phase finishes. 4. Track the best subset found so far.

Maintain:

• max_length, the size of the largest subset found
• max_index, the ending index of that subset

5. Iterate through each position i.

For every i, examine all earlier positions j where 0 <= j < i. 6. Check divisibility.

If nums[i] % nums[j] == 0, then nums[i] can extend the subset ending at j. 7. Update the dynamic programming state.

If extending the chain at j produces a longer subset than the current best ending at i, update:

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

8. Update the global maximum.

If dp[i] exceeds max_length, store the new best length and ending index. 9. Reconstruct the answer.

Starting from max_index, repeatedly follow the parent links backward until reaching -1. 10. Reverse the reconstructed list.

Because reconstruction proceeds backward through the chain, reverse the result before returning it.

Why it works

After sorting, every valid divisible subset can be viewed as a chain where each element divides the next one. The dynamic programming recurrence guarantees that dp[i] always stores the largest valid chain ending at nums[i].

Since every possible predecessor j < i is examined, the algorithm never misses a valid extension. The parent pointers preserve the exact chain used to construct the optimal solution, allowing correct reconstruction at the end.

Python Solution

from typing import List

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        if not nums:
            return []

        nums.sort()
        n = len(nums)

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

        max_length = 1
        max_index = 0

        for i in range(n):
            for j in range(i):
                if nums[i] % nums[j] == 0:
                    if dp[j] + 1 > dp[i]:
                        dp[i] = dp[j] + 1
                        parent[i] = j

            if dp[i] > max_length:
                max_length = dp[i]
                max_index = i

        result = []

        while max_index != -1:
            result.append(nums[max_index])
            max_index = parent[max_index]

        result.reverse()
        return result

The implementation begins by sorting the array so divisibility chains can be built from left to right.

The dp array tracks the length of the best divisible subset ending at each index. Initially, every value is 1 because each number can form a subset by itself.

The parent array records which earlier number produced the best chain for each position. This is necessary because dynamic programming alone only stores lengths, not the actual subset.

The nested loops examine all earlier values for each current position. Whenever a divisible predecessor is found, the algorithm checks whether extending that chain improves the current best result.

After the dynamic programming phase completes, the algorithm reconstructs the answer by walking backward through the parent array starting from max_index.

Finally, the reconstructed chain is reversed because reconstruction proceeds from largest element to smallest.

Go Solution

package main

import (
	"sort"
)

func largestDivisibleSubset(nums []int) []int {
	if len(nums) == 0 {
		return []int{}
	}

	sort.Ints(nums)

	n := len(nums)

	dp := make([]int, n)
	parent := make([]int, n)

	for i := 0; i < n; i++ {
		dp[i] = 1
		parent[i] = -1
	}

	maxLength := 1
	maxIndex := 0

	for i := 0; i < n; i++ {
		for j := 0; j < i; j++ {
			if nums[i]%nums[j] == 0 {
				if dp[j]+1 > dp[i] {
					dp[i] = dp[j] + 1
					parent[i] = j
				}
			}
		}

		if dp[i] > maxLength {
			maxLength = dp[i]
			maxIndex = i
		}
	}

	result := []int{}

	for maxIndex != -1 {
		result = append(result, nums[maxIndex])
		maxIndex = parent[maxIndex]
	}

	for left, right := 0, len(result)-1; left < right; left, right = left+1, right-1 {
		result[left], result[right] = result[right], result[left]
	}

	return result
}

The Go implementation follows the same logic as the Python version. The primary differences are related to language syntax and slice handling.

Go requires explicit initialization of arrays and uses sort.Ints(nums) for sorting. The result reconstruction uses a manual slice reversal because Go does not provide a built-in reverse function for slices.

Integer overflow is not a concern because divisibility checks only use modulo operations on values within the problem constraints.

Worked Examples

Example 1

Input:

nums = [1,2,3]

After sorting:

[1,2,3]

Initial state:

Index	Value	dp	parent
0	1	1	-1
1	2	1	-1
2	3	1	-1

Processing i = 1:

• Check j = 0
• 2 % 1 == 0

Update:

dp[1] = dp[0] + 1 = 2
parent[1] = 0

State now:

Index	Value	dp	parent
0	1	1	-1
1	2	2	0
2	3	1	-1

Processing i = 2:

• Check j = 0
• 3 % 1 == 0

Update:

dp[2] = 2
parent[2] = 0

• Check j = 1
• 3 % 2 != 0

Final state:

Index	Value	dp	parent
0	1	1	-1
1	2	2	0
2	3	2	0

Maximum chain length is 2.

Reconstruction from index 1:

2 -> 1

Reverse result:

[1,2]

Example 2

Input:

nums = [1,2,4,8]

Sorted array:

[1,2,4,8]

Dynamic programming progression:

i	nums[i]	Best Previous	dp[i]	parent[i]
0	1	none	1	-1
1	2	1	2	0
2	4	2	3	1
3	8	4	4	2

Reconstruction:

8 -> 4 -> 2 -> 1

Reverse result:

[1,2,4,8]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n^2)	Every pair of indices is checked once
Space	O(n)	dp, parent, and reconstruction storage

The sorting step costs O(n log n), but the nested dynamic programming loops dominate the runtime with O(n^2) complexity.

The space usage is linear because the algorithm stores only a few arrays of size n.

Test Cases

from typing import List

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        if not nums:
            return []

        nums.sort()
        n = len(nums)

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

        max_length = 1
        max_index = 0

        for i in range(n):
            for j in range(i):
                if nums[i] % nums[j] == 0:
                    if dp[j] + 1 > dp[i]:
                        dp[i] = dp[j] + 1
                        parent[i] = j

            if dp[i] > max_length:
                max_length = dp[i]
                max_index = i

        result = []

        while max_index != -1:
            result.append(nums[max_index])
            max_index = parent[max_index]

        result.reverse()
        return result

solution = Solution()

# Provided example with multiple valid answers
assert len(solution.largestDivisibleSubset([1, 2, 3])) == 2

# Entire array forms a divisible chain
assert solution.largestDivisibleSubset([1, 2, 4, 8]) == [1, 2, 4, 8]

# Single element array
assert solution.largestDivisibleSubset([7]) == [7]

# No divisible relationships beyond single elements
result = solution.largestDivisibleSubset([2, 3, 5, 7, 11])
assert len(result) == 1

# Larger divisible chain
assert solution.largestDivisibleSubset([1, 3, 6, 24]) == [1, 3, 6, 24]

# Multiple valid chains
result = solution.largestDivisibleSubset([1, 2, 4, 8, 9, 72])
assert len(result) >= 5

# Unsorted input
assert solution.largestDivisibleSubset([8, 4, 2, 1]) == [1, 2, 4, 8]

# Large values
assert solution.largestDivisibleSubset([1, 1000000000]) == [1, 1000000000]

# Chain with gaps
assert solution.largestDivisibleSubset([1, 16, 7, 8, 4]) == [1, 4, 8, 16]

# Two equally long valid answers
result = solution.largestDivisibleSubset([1, 2, 3, 6])
assert len(result) == 3

Test	Why
[1,2,3]	Validates multiple acceptable answers
[1,2,4,8]	Tests a complete divisible chain
[7]	Tests smallest possible input
[2,3,5,7,11]	Tests when no pair divides another
[1,3,6,24]	Tests longer chain construction
[1,2,4,8,9,72]	Tests branching possibilities
[8,4,2,1]	Ensures sorting is handled correctly
[1,1000000000]	Tests large integer handling
[1,16,7,8,4]	Tests reconstruction through non-adjacent values
[1,2,3,6]	Tests cases with multiple optimal chains

Edge Cases

Single Element Input

An array containing only one number is always valid because there are no conflicting pairs to check. A buggy implementation might incorrectly assume at least two elements are needed for a divisible relationship.

This implementation handles the case naturally because every element starts with dp[i] = 1, meaning each number forms a valid subset on its own.

No Divisible Pairs

Consider input like [2,3,5,7]. None of these values divide one another.

A naive chain-building algorithm might accidentally return invalid combinations if it does not carefully verify divisibility before extending subsets.

This solution checks nums[i] % nums[j] == 0 before every transition, ensuring only valid chains are constructed. The result becomes any single-element subset.

Multiple Optimal Answers

Some inputs have several equally large valid subsets. For example:

[1,2,3,6]

Both [1,2,6] and [1,3,6] are valid answers.

An incorrect implementation might assume the answer is unique and accidentally overwrite valid reconstruction data.

This implementation simply returns the first maximum chain it discovers. Since the problem explicitly allows returning any valid largest subset, this behavior is correct.

Unsorted Input

The input array may appear in arbitrary order, such as [8,1,4,2].

Without sorting, divisibility chains become difficult to build consistently because larger divisible values may appear before smaller base values.

Sorting guarantees that when processing nums[i], all possible predecessors already appear earlier in the array. This is what makes the dynamic programming transition valid and efficient.