Largest Divisible Subset

Med

#0355Time: O(2^N * N^2). There are `2^N` subsets. For each subset of size `K`, the validation check takes `O(K^2)` pairwise comparisons. The average subset size is `N/2`, leading to this complexity.Space: O(N). The space is required to store the `currentSubset` and the `largestSubset` found. Each can have a maximum size of `N`.

Patterns

Math Dynamic Programming

Algorithms

Sorting

Data structures

Array

Prompt

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 1:

Input: nums = [1,2,3]
Output: [1,2]
Explanation: [1,3] is also accepted.

Example 2:

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

Constraints:

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

Approaches

2 approaches with complexity analysis and trade-offs.

This naive approach involves generating every possible subset of the input array nums. For each subset, we check if it satisfies the divisible subset property, where for any pair of elements, one must divide the other. We keep track of the largest valid subset found.

Algorithm

Initialize an empty list largestSubset to store the result.
Let N be the number of elements in nums.
Loop through all integers from 0 to 2^N - 1. Each integer i acts as a bitmask.
For each i, create a currentSubset:
- Iterate from j = 0 to N-1.
- If the j-th bit of i is set, add nums[j] to currentSubset.
Check if currentSubset is a valid divisible subset:
- Assume it's valid (isValid = true).
- Iterate through all pairs of elements (a, b) in currentSubset.
- If a % b != 0 and b % a != 0, set isValid = false and break the loops.
If isValid is true and currentSubset.size() > largestSubset.size(), update largestSubset = currentSubset.
After checking all 2^N possibilities, return largestSubset.

Walkthrough

The core idea is to explore the entire solution space. The number of subsets of a set with N elements is 2^N. We can represent each subset using a bitmask of length N. For each bitmask, we construct the corresponding subset. Then, we perform a validation check on this subset. The validation involves iterating through all pairs of numbers in the subset and checking the divisibility condition. If a subset is valid, we compare its size with the largest one found so far and update if necessary. While simple to conceptualize, this method is computationally expensive and impractical for the given constraints.

Complexity

Time

O(2^N * N^2). There are `2^N` subsets. For each subset of size `K`, the validation check takes `O(K^2)` pairwise comparisons. The average subset size is `N/2`, leading to this complexity.

Space

O(N). The space is required to store the `currentSubset` and the `largestSubset` found. Each can have a maximum size of `N`.

Trade-offs

Pros

Conceptually simple and easy to understand.

Cons

Extremely inefficient.
Feasible only for very small N (e.g., N < 20).
Will result in a 'Time Limit Exceeded' error for the given problem constraints.

A much more efficient approach is to use dynamic programming, which is well-suited for problems with optimal substructure. The strategy is similar to solving the Longest Increasing Subsequence (LIS) problem. By first sorting the input array, we can build the solution iteratively.

Algorithm

If the input array nums is empty, return an empty list.
Sort the array nums in non-decreasing order.
Initialize an integer array dp of size N, with all elements set to 1. dp[i] will store the length of the largest divisible subset ending at nums[i].
Initialize an integer array prev of size N, with all elements set to -1. prev[i] will store the index of the previous element in the largest divisible subset ending at nums[i].
Initialize maxIndex = 0 to track the index of the last element of the largest subset found so far.
Iterate through nums from i = 0 to N-1:
- For each i, iterate from j = 0 to i-1:
  - If nums[i] is divisible by nums[j] and dp[j] + 1 is greater than dp[i]:
    - Update dp[i] = dp[j] + 1.
    - Update prev[i] = j.
- If dp[i] is greater than dp[maxIndex], update maxIndex = i.
Reconstruct the result list:
- Initialize an empty list result.
- Start with k = maxIndex.
- While k is not -1:
  - Add nums[k] to result.
  - Update k = prev[k].
Return the result list.

Walkthrough

The key insight is that if we sort the input array nums, any valid divisible subset, when sorted, will have the property that each element is divisible by the preceding element. This transforms the problem into finding the longest such sequence.

We use a DP array, dp, where dp[i] stores the size of the largest divisible subset that ends with the element nums[i]. To compute dp[i], we look at all previous elements nums[j] (where j < i). If nums[i] is divisible by nums[j], it means we can potentially extend the subset ending at nums[j]. We choose the j that gives the maximum length, so dp[i] = 1 + max(dp[j]) for all valid j.

To reconstruct the actual subset, we use an auxiliary array, prev, where prev[i] stores the index of the element that precedes nums[i] in the longest divisible subset. After filling the dp and prev arrays, we find the index corresponding to the maximum value in dp and backtrack using the prev array to build the result.

1import java.util.ArrayList;2import java.util.Arrays;3import java.util.List;4 5public class Solution {6    public List<Integer> largestDivisibleSubset(int[] nums) {7        int n = nums.length;8        if (n == 0) {9            return new ArrayList<>();10        }11 12        Arrays.sort(nums);13 14        int[] dp = new int[n];15        Arrays.fill(dp, 1);16        int[] prev = new int[n];17        Arrays.fill(prev, -1);18 19        int maxIndex = 0;20 21        for (int i = 0; i < n; i++) {22            for (int j = 0; j < i; j++) {23                if (nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]) {24                    dp[i] = dp[j] + 1;25                    prev[i] = j;26                }27            }28            if (dp[i] > dp[maxIndex]) {29                maxIndex = i;30            }31        }32 33        List<Integer> result = new ArrayList<>();34        int k = maxIndex;35        while (k != -1) {36            result.add(nums[k]);37            k = prev[k];38        }39 40        return result;41    }42}

Complexity

Time

O(N^2). Sorting the array takes `O(N log N)`. The nested loops for the DP calculation take `O(N^2)`. Reconstructing the path takes `O(N)`. The overall complexity is dominated by the `O(N^2)` part.

Space

O(N). We use two arrays, `dp` and `prev`, each of size `N`. The list for the result also requires up to `O(N)` space.

Trade-offs

Pros

Efficient enough to pass for the given constraints.
Guarantees finding the largest divisible subset.
It's a standard and well-understood dynamic programming pattern.

Cons

Requires extra space for DP and predecessor arrays.
The O(N^2) time complexity might be a bottleneck for significantly larger inputs beyond the problem's constraints.

Solutions

Solution

1class Solution { public List < Integer > largestDivisibleSubset ( int [] nums ) { Arrays . sort ( nums ); int n = nums . length ; int [] f = new int [ n ]; Arrays . fill ( f , 1 ); int k = 0 ; for ( int i = 0 ; i < n ; ++ i ) { for ( int j = 0 ; j < i ; ++ j ) { if ( nums [ i ] % nums [ j ] == 0 ) { f [ i ] = Math . max ( f [ i ], f [ j ] + 1 ); } } if ( f [ k ] < f [ i ]) { k = i ; } } int m = f [ k ]; List < Integer > ans = new ArrayList <>(); for ( int i = k ; m > 0 ; -- i ) { if ( nums [ k ] % nums [ i ] == 0 && f [ i ] == m ) { ans . add ( nums [ i ]); k = i ; -- m ; } } return ans ; } }

1class Solution {2public:3  vector<int> largestDivisibleSubset(vector<int> &nums) {4    sort(nums.begin(), nums.end());5    int n = nums.size();6    int f[n];7    int k = 0;8    for (int i = 0; i < n; ++i) {9      f[i] = 1;10      for (int j = 0; j < i; ++j) {11        if (nums[i] % nums[j] == 0) {12          f[i] = max(f[i], f[j] + 1);13        }14      }15      if (f[k] < f[i]) {16        k = i;17      }18    }19    int m = f[k];20    vector<int> ans;21    for (int i = k; m > 0; --i) {22      if (nums[k] % nums[i] == 0 && f[i] == m) {23        ans.push_back(nums[i]);24        k = i;25        --m;26      }27    }28    return ans;29  }30};

1class Solution : def largestDivisibleSubset ( self , nums : List [ int ]) -> List [ int ]: nums . sort () n = len ( nums ) dp = [ 0 ] * n parent = [ 0 ] * n max_index , max_length = 0 , 0 for i in range ( n - 1 , - 1 , - 1 ): for j in range ( i , n ): # note: not i+1, for i==j length is 1 if nums [ j ] % nums [ i ] == 0 and dp [ i ] < 1 + dp [ j ]: dp [ i ] = 1 + dp [ j ] parent [ i ] = j if dp [ i ] > max_length : max_length = dp [ i ] max_index = i res = [] for _ in range ( max_length ): res . append ( nums [ max_index ]) max_index = parent [ max_index ] return res ################ 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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem