Largest Divisible Subset solution and explanation
Google
9 more videos on this problem
Largest Divisible Subset | Dynamic programming | Leetcode #368Techdose · 17:06 · 28K views
Largest Divisible Subset - Leetcode 368 - PythonNeetCodeIO · 22:57 · 19K views
Largest Divisible Subset - Leetcode 368 - PythonNeetCodeIO · 22:57 · 14K views
Largest Divisible Subset | Leetcode 368Techdose · 20:09 · 4K views
368. Largest Divisible Subset (updated video in description) (Leetcode Medium)Programming Live with Larry · 18:24 · 2K views
Leetcode 368 Largest Divisible SubsetRen Zhang · 13:29 · 462 views
Largest Divisible Subset - Python - Leetcode 368CheatCode Ninja · 10:13 · 354 views
368. Largest Divisible Subset - June LeetCode ChallengeGame of Coders · 15:11 · 244 views
368. Largest Divisible Subset | Leetcode Daily - PythonLeetcode Daily · 11:10 · 209 views
Largest Divisible Subset - Facebook interview question | Leetcode#368 | Python solutionTanay Chauli · 19:55 · 139 views
The problem
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, oranswer[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 <= 10001 <= nums[i] <= 2 * 109- All the integers in
numsare unique.
Approach overview
Problem Overview: Given a set of distinct positive integers, return the largest subset where for every pair (a, b), either a % b == 0 or b % a == 0. The task is essentially finding the longest chain where each number divides the next.
Approach 1: Backtracking with Pruning (Exponential Time)
This approach generates subsets using recursive backtracking and keeps only those where every newly added number is divisible with the last chosen element. Sorting the array first helps prune invalid branches early because divisibility relationships become easier to check in order. At each step you either include the current number if it satisfies the divisibility rule or skip it. This brute-force search explores many combinations, resulting in O(2^n) time in the worst case and O(n) recursion space.
Approach 2: Dynamic Programming with Sorting (O(n^2) time)
The optimal solution sorts the array first, which guarantees that if nums[i] % nums[j] == 0 for j < i, then nums[j] can appear before nums[i] in a valid divisible chain. Use a DP array where dp[i] stores the size of the largest divisible subset ending at index i. For each element, iterate through all previous elements and extend the chain if the divisibility condition holds. Maintain a parent array to reconstruct the subset after computing the maximum length. This approach runs in O(n^2) time and requires O(n) extra space for the DP and reconstruction arrays.
The key insight is that after sorting, the problem becomes similar to a longest increasing subsequence variant where the transition condition is divisibility instead of ordering. Each number attempts to extend the best chain formed by smaller numbers.
Core techniques involved include sorting to establish order, dynamic programming for optimal substructure, and simple arithmetic checks from math properties of divisibility.
Recommended for interviews: The dynamic programming with sorting approach is the expected solution. Interviewers want to see recognition of the LIS-style DP pattern and the ability to reconstruct the subset using parent pointers. Backtracking demonstrates baseline reasoning but does not scale well for larger inputs.
Approach 1: Dynamic Programming with Sorting
This approach utilizes dynamic programming along with sorting to find the largest subset where each pair of elements is divisible by the other. The core idea is to sort the array, then use a dynamic programming array to keep track of the size of the largest divisible subset that ends at each element. We also maintain a path array to help reconstruct the subset.
def largestDivisibleSubset(nums):
if not nums:
return []
nums.sort()
dp = [[num] for num in nums]
for i in range(len(nums)):
for j in range(i):
if nums[i] % nums[j] == 0 and len(dp[j]) + 1 > len(dp[i]):
dp[i] = dp[j] + [nums[i]]
return max(dp, key=len)import java.util.*;
public class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
if (nums.length == 0) return new ArrayList<>();
Arrays.sort(nums);
List<Integer>[] dp = new ArrayList[nums.length];
List<Integer> maxSubset = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
List<Integer> subset = new ArrayList<>();
for (int k = 0; k < i; k++) {
if (nums[i] % nums[k] == 0 && dp[k].size() > subset.size()) {
subset = new ArrayList<>(dp[k]);
}
}
subset.add(nums[i]);
dp[i] = subset;
if (dp[i].size() > maxSubset.size()) {
maxSubset = dp[i];
}
}
return maxSubset;
}
}#include <vector>
#include <algorithm>
using namespace std;
vector<int> largestDivisibleSubset(vector<int>& nums) {
if (nums.empty()) return {};
sort(nums.begin(), nums.end());
int n = nums.size();
vector<int> dp(n, 1), previous(n, -1);
int maxSize = 1, maxIndex = 0;
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[i] % nums[j] == 0 && dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1;
previous[i] = j;
}
}
if (dp[i] > maxSize) {
maxSize = dp[i];
maxIndex = i;
}
}
vector<int> result;
for (int i = maxIndex; i >= 0; i = previous[i])
result.push_back(nums[i]);
reverse(result.begin(), result.end());
return result;
}var largestDivisibleSubset = function(nums) {
if (nums.length === 0) return [];
nums.sort((a, b) => a - b);
let dp = Array.from({ length: nums.length }, () => []);
for (let i = 0; i < nums.length; i++) {
dp[i] = [nums[i]];
for (let j = 0; j < i; j++) {
if (nums[i] % nums[j] === 0 && dp[j].length + 1 > dp[i].length) {
dp[i] = dp[j].concat(nums[i]);
}
}
}
return dp.reduce((max, curr) => curr.length > max.length ? curr : max, []);
};#include <stdio.h>
#include <stdlib.h>
int* largestDivisibleSubset(int* nums, int numsSize, int* returnSize) {
if (numsSize == 0) {
*returnSize = 0;
return NULL;
}
qsort(nums, numsSize, sizeof(int), compare);
int *dp = (int *)malloc(sizeof(int) * numsSize);
int *previous = (int *)malloc(sizeof(int) * numsSize);
int maxSize = 0, maxIndex = -1;
for (int i = 0; i < numsSize; i++) {
dp[i] = 1;
previous[i] = -1;
for (int j = 0; j < i; j++) {
if (nums[i] % nums[j] == 0 && dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1;
previous[i] = j;
}
}
if (dp[i] > maxSize) {
maxSize = dp[i];
maxIndex = i;
}
}
int *result = (int *)malloc(sizeof(int) * maxSize);
int pointer = maxIndex;
*returnSize = maxSize;
for (int k = maxSize - 1; k >= 0; k--) {
result[k] = nums[pointer];
pointer = previous[pointer];
}
free(dp);
free(previous);
return result;
}
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}using System;
using System.Collections.Generic;
public class Solution {
public IList<int> LargestDivisibleSubset(int[] nums) {
int n = nums.Length;
if (n == 0) return new List<int>();
Array.Sort(nums);
List<int>[] dp = new List<int>[n];
for (int i = 0; i < n; i++) dp[i] = new List<int>();
for (int i = 0; i < n; i++) {
List<int> maxSubset = new List<int>();
for (int j = 0; j < i; j++) {
if (nums[i] % nums[j] == 0 && dp[j].Count > maxSubset.Count) {
maxSubset = new List<int>(dp[j]);
}
}
dp[i] = maxSubset;
dp[i].Add(nums[i]);
}
List<int> result = new List<int>();
foreach (var subset in dp) {
if (subset.Count > result.Count) result = subset;
}
return result;
}
}This Python function begins by handling the edge case of an empty nums. It sorts the array and initializes a dynamic list dp where each entry starts with the single number subset. For each number, previous elements are checked, and if they divide the current number, the subset is expanded by appending the current number. Finally, the longest subset from dp is returned.
Time Complexity: O(n^2), nested loops for comparing divisibility between each pair of numbers.
Space Complexity: O(n^2), due to storage of multiple subsets in dp.
Approach 2: Backtracking with Pruning
This approach leverages backtracking with pruning to explore subsets and constrain exploration using the divisibility constraint. It uses a sorted array to systematically explore subsets and prune paths early when constraints are no longer satisfied, allowing potentially faster exploration compared to the dynamic programming approach, especially in tightly constrained subsets.
/* This backtracking approach would ... *//* This backtracking approach would ... *//* This backtracking approach would ... *//* This backtracking approach would ... *//* This backtracking approach would ... *//* This backtracking approach would ... */...
...
Approach 3: Default Approach
function largestDivisibleSubset(nums: number[]): number[] {
nums.sort((a, b) => a - b);
const n = nums.length;
const f: number[] = Array(n).fill(1);
let k = 0;
for (let i = 0; i < n; ++i) {
for (let 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;
}
}
let m = f[k];
const ans: number[] = [];
for (let i = k; m > 0; --i) {
if (nums[k] % nums[i] === 0 && f[i] === m) {
ans.push(nums[i]);
k = i;
--m;
}
}
return ans;
}func largestDivisibleSubset(nums []int) (ans []int) {
sort.Ints(nums)
n := len(nums)
f := make([]int, n)
k := 0
for i := 0; i < n; i++ {
f[i] = 1
for j := 0; j < i; j++ {
if nums[i]%nums[j] == 0 {
f[i] = max(f[i], f[j]+1)
}
}
if f[k] < f[i] {
k = i
}
}
m := f[k]
for i := k; m > 0; i-- {
if nums[k]%nums[i] == 0 && f[i] == m {
ans = append(ans, nums[i])
k = i
m--
}
}
return
}impl Solution {
pub fn largest_divisible_subset(nums: Vec<i32>) -> Vec<i32> {
let mut nums = nums;
nums.sort();
let n = nums.len();
let mut f = vec![1; n];
let mut k = 0;
for i in 0..n {
for j in 0..i {
if nums[i] % nums[j] == 0 {
f[i] = f[i].max(f[j] + 1);
}
}
if f[k] < f[i] {
k = i;
}
}
let mut m = f[k];
let mut ans = Vec::new();
for i in (0..=k).rev() {
if nums[k] % nums[i] == 0 && f[i] == m {
ans.push(nums[i]);
k = i;
m -= 1;
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with Sorting | Time Complexity: O(n^2), nested loops for comparing divisibility between each pair of numbers. |
| Backtracking with Pruning | ... |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Pruning | O(2^n) | O(n) | Useful for understanding subset generation or when input size is very small |
| Dynamic Programming with Sorting | O(n^2) | O(n) | Best general solution for interview settings and typical constraints |
Frequently asked questions
Is Largest Divisible Subset easy or hard?
Largest Divisible Subset is usually classified as a Medium problem. The main difficulty is recognizing that sorting transforms the problem into a longest-chain dynamic programming pattern similar to Longest Increasing Subsequence.
How to solve Largest Divisible Subset in O(n)?
An O(n) solution is not known for the general problem because every number may need to be compared with earlier elements to determine divisibility relationships. The standard optimal approach sorts the array and applies dynamic programming in O(n^2) time.
What is the best approach for Largest Divisible Subset?
The best approach uses sorting followed by dynamic programming. After sorting the numbers, compute the longest divisible chain ending at each index using a DP array and track parent pointers to rebuild the subset. This runs in O(n^2) time and O(n) space, which is efficient for the typical constraints of the problem.
Is Largest Divisible Subset asked at Google/Amazon/Meta?
Largest Divisible Subset is a common dynamic programming interview problem and has appeared in interview preparation lists for companies like Amazon, Google, and Meta. It tests recognition of LIS-style DP patterns and the ability to reconstruct sequences from DP states.
What data structure is used in Largest Divisible Subset?
The solution mainly uses arrays for dynamic programming and parent tracking. After sorting the input array, a DP array stores the size of the best divisible subset ending at each index, while another array reconstructs the subset path.
What is the time complexity of Largest Divisible Subset?
The optimal dynamic programming solution runs in O(n^2) time because each element checks divisibility with all previous elements after sorting. Space complexity is O(n) for storing DP values and parent pointers used to reconstruct the subset.
Largest Divisible Subset Python or Java solution approach?
Both Python and Java implementations follow the same pattern: sort the array, compute a DP array where dp[i] stores the length of the divisible chain ending at i, and maintain parent pointers. After identifying the maximum DP value, reconstruct the subset by tracing the parent indices.