249. Largest Divisible Subset
🔗 LeetCode Problem: 368. Largest Divisible Subset
📊 Difficulty: Medium
🏷️ Topics: Array, Math, Dynamic Programming, Sorting, DP - LIS
Problem Statement
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 <= 1000
- 1 <= nums[i] <= 2 * 10^9
- All the integers in nums are unique.
🧒 Let's Build Understanding from Absolute Scratch
What Does "Divisible" Even Mean?
Before anything else, let's understand divisibility!
What does "a divides b" mean?
It means: b % a == 0
Or: b is a multiple of a
Or: b = k × a for some integer k
Examples:
4 divides 12? YES! Because 12 = 3 × 4, and 12 % 4 = 0
3 divides 12? YES! Because 12 = 4 × 3, and 12 % 3 = 0
5 divides 12? NO! Because 12 % 5 = 2 (remainder!)
Simple! ✓
What Does This Problem REALLY Ask?
Let me start with the SIMPLEST example:
Given: nums = [1, 2]
Question: Find a subset where EVERY PAIR divides each other?
Let's check:
Subset [1, 2]:
Does 1 divide 2? 2 % 1 = 0 ✓ YES!
Does 2 divide 1? 1 % 2 = 1 ✗ NO!
But wait! The problem says "every pair (answer[i], answer[j])" satisfies:
answer[i] % answer[j] == 0, OR
answer[j] % answer[i] == 0
So we need AT LEAST ONE direction to work!
For [1, 2]:
2 % 1 = 0 ✓ (one direction works!)
So [1, 2] is VALID! ✓
Let's try [1, 2, 3]:
Pair (1, 2): 2 % 1 = 0 ✓
Pair (1, 3): 3 % 1 = 0 ✓
Pair (2, 3):
2 % 3 = 2 ✗
3 % 2 = 1 ✗
NEITHER direction works! ✗
So [1, 2, 3] is INVALID! ✗
Let's try [1, 2, 4]:
Pair (1, 2): 2 % 1 = 0 ✓
Pair (1, 4): 4 % 1 = 0 ✓
Pair (2, 4): 4 % 2 = 0 ✓
All pairs work! [1, 2, 4] is VALID! ✓
INSIGHT: We need EVERY pair to have divisibility! 🔑
Discovering The Pattern - Why Order Matters
I notice something:
In [1, 2, 4]:
1 < 2 < 4 (increasing order)
1 divides 2
2 divides 4
And automatically: 1 divides 4!
In [1, 3, 5]:
1 < 3 < 5 (increasing order)
1 divides 3
1 divides 5
But 3 does NOT divide 5! ✗
Let me think... If I SORT numbers: a < b < c
Then for divisibility:
- Smaller numbers can divide larger numbers
- Larger numbers CANNOT divide smaller numbers
So I only need to check: larger % smaller = 0
Example with [2, 4, 8]:
Check: 4 % 2 = 0 ✓
Check: 8 % 4 = 0 ✓
Do I need to check 8 % 2?
Well, if 4 = 2×k₁ and 8 = 4×k₂
Then 8 = (2×k₁)×k₂ = 2×(k₁×k₂)
So 8 % 2 = 0 automatically! ✓
This is TRANSITIVITY!
If a divides b, and b divides c
Then a divides c! 🔑
So after sorting:
I only check consecutive pairs!
a → b → c
Just check: b%a=0 and c%b=0
Then c%a=0 is FREE! ✓
This makes the problem MUCH simpler! ✓
Building More Intuition - The Chain Analogy
Think of divisible subset as a CHAIN:
Valid chain: 1 → 2 → 4 → 8
Each link divides by previous: 2%1=0, 4%2=0, 8%4=0 ✓
Invalid chain: 1 → 2 → 5
Last link breaks: 5%2=1 ✗
Another valid chain: 1 → 3 → 9 → 27
Each link works: 3%1=0, 9%3=0, 27%9=0 ✓
So the problem becomes:
Find the LONGEST valid chain! 🔑
This sounds like... Longest Increasing Subsequence!
LIS: Find longest chain where each > previous
This: Find longest chain where each divides by previous!
SAME structure, different condition! ✓
The Key Insight - It's Just Modified LIS!
Comparing side by side:
LONGEST INCREASING SUBSEQUENCE:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Problem: Find longest chain where nums[i] < nums[j]
Approach:
1. For each position i
2. Check all positions j < i
3. If nums[j] < nums[i]: can extend!
4. Track maximum
LARGEST DIVISIBLE SUBSET:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Problem: Find longest chain where nums[i] % nums[j] == 0
Approach:
1. SORT FIRST! (so we go small to large)
2. For each position i
3. Check all positions j < i
4. If nums[i] % nums[j] == 0: can extend!
5. Track maximum
Only difference: The condition!
LIS: nums[j] < nums[i]
This: nums[i] % nums[j] == 0
Both are O(n²) DP! ✓
NEW CHALLENGE: Return the actual elements, not just length!
We need to track: WHERE did each element come from?
Use a "parent" array! 🔑
Simple Example - Building Understanding Step By Step
Let's work through: nums = [1, 2, 4]
STEP 1: Sort (already sorted)
[1, 2, 4]
STEP 2: What do we track?
dp[i] = length of longest chain ENDING at position i
For position 0 (value 1):
Can't extend anything → dp[0] = 1 (just itself)
For position 1 (value 2):
Can I extend from position 0?
2 % 1 = 0 ✓ YES!
So chain [1] becomes [1, 2]
dp[1] = dp[0] + 1 = 2
For position 2 (value 4):
Can I extend from position 0?
4 % 1 = 0 ✓ YES! → length would be 2
Can I extend from position 1?
4 % 2 = 0 ✓ YES! → length would be 3 ← BETTER!
Take the best!
dp[2] = 3
Final: dp = [1, 2, 3]
Maximum length = 3
Great! But which elements form this chain?
That's where we need to track "parent"! 🔑
Adding Parent Tracking - The Missing Piece
Let's redo with parent tracking:
nums = [1, 2, 4]
Initialize:
dp[i] = 1 for all (each element alone)
parent[i] = -1 for all (no parent yet)
Position 0 (value 1):
dp[0] = 1
parent[0] = -1 (no one before me)
Position 1 (value 2):
Check position 0:
2 % 1 = 0 ✓
Can extend! dp[1] = dp[0] + 1 = 2
Mark: parent[1] = 0 (I came from position 0!)
Position 2 (value 4):
Check position 0:
4 % 1 = 0 ✓
Length = 2, parent would be 0
Check position 1:
4 % 2 = 0 ✓
Length = 3 ← BETTER!
Update: parent[2] = 1 (I came from position 1!)
dp[2] = 3, parent[2] = 1
Arrays:
dp = [1, 2, 3]
parent = [-1, 0, 1]
Now to get the actual subset:
Start at best position (index 2, value 4)
parent[2] = 1 → go to position 1 (value 2)
parent[1] = 0 → go to position 0 (value 1)
parent[0] = -1 → STOP!
Path backwards: 2 → 1 → 0
Values: 4 → 2 → 1
Reverse: [1, 2, 4] ✓
Perfect! We reconstructed the chain! 🎉
🤔 Building Intuition - The Complete Mental Model
Let's Work Through A Medium Example Together
nums = [4, 8, 10, 240]
First question: Is this sorted?
No! Let me sort it first.
After sort: [4, 8, 10, 240]
Now let me think about divisibility chains:
Can I make chain [4, 8]?
8 % 4 = 0 ✓ YES!
Can I make chain [4, 8, 10]?
8 % 4 = 0 ✓
10 % 8 = 2 ✗ NO!
Chain breaks at 10!
Can I make chain [4, 8, 240]?
8 % 4 = 0 ✓
240 % 8 = 0 ✓ YES!
Do I need to check 240 % 4?
No! Transitivity tells us it's automatic!
If 8 = 2×4 and 240 = 30×8
Then 240 = 30×2×4 = 60×4 ✓
So [4, 8, 240] is valid with length 3!
Can I make chain [4, 10]?
10 % 4 = 2 ✗ NO!
Can I make chain [10, 240]?
240 % 10 = 0 ✓ YES! Length 2
Comparing all chains:
[4] → length 1
[8] → length 1
[10] → length 1
[240] → length 1
[4, 8] → length 2
[4, 8, 240] → length 3 ← WINNER!
[10, 240] → length 2
Best: [4, 8, 240] with length 3 ✓
Now Let's Build This With DP
I'll track two things:
dp[i] = length of longest chain ENDING at index i
parent[i] = which index did I extend from?
nums = [4, 8, 10, 240]
indices: 0 1 2 3
Initialize:
dp = [1, 1, 1, 1] (each element alone)
parent = [-1, -1, -1, -1] (no parent yet)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
PROCESS INDEX 0 (value 4):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
No previous elements to extend from.
dp[0] = 1
parent[0] = -1
State:
dp = [1, ?, ?, ?]
parent = [-1, ?, ?, ?]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
PROCESS INDEX 1 (value 8):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Check previous indices:
j=0 (value 4):
Can I extend from j=0?
Check: 8 % 4 = 0 ✓ YES!
If I extend:
Length = dp[0] + 1 = 1 + 1 = 2
Current best at i=1 is dp[1]=1
New option is 2 → BETTER!
Update:
dp[1] = 2
parent[1] = 0 (came from index 0)
State:
dp = [1, 2, ?, ?]
parent = [-1, 0, ?, ?]
Meaning: Chain [4, 8] with length 2 ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
PROCESS INDEX 2 (value 10):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Check previous indices:
j=0 (value 4):
10 % 4 = 2 ✗ NO!
Can't extend from here.
j=1 (value 8):
10 % 8 = 2 ✗ NO!
Can't extend from here either.
No valid extension!
dp[2] = 1 (stays alone)
parent[2] = -1
State:
dp = [1, 2, 1, ?]
parent = [-1, 0, -1, ?]
Meaning: 10 doesn't fit into any chain! ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
PROCESS INDEX 3 (value 240):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Check previous indices:
j=0 (value 4):
240 % 4 = 0 ✓ YES!
If extend: length = dp[0] + 1 = 1 + 1 = 2
Current best: dp[3] = 1
This gives: 2 → BETTER!
Update:
dp[3] = 2
parent[3] = 0
j=1 (value 8):
240 % 8 = 0 ✓ YES!
If extend: length = dp[1] + 1 = 2 + 1 = 3
Current best: dp[3] = 2
This gives: 3 → EVEN BETTER!
Update:
dp[3] = 3
parent[3] = 1 (NOW coming from index 1!)
j=2 (value 10):
240 % 10 = 0 ✓ YES!
If extend: length = dp[2] + 1 = 1 + 1 = 2
Current best: dp[3] = 3
This gives: 2 → WORSE than what we have
No update.
Final for index 3:
dp[3] = 3
parent[3] = 1
State:
dp = [1, 2, 1, 3]
parent = [-1, 0, -1, 1]
WHY parent[3] = 1?
Because extending from index 1 (value 8)
gives us the LONGEST chain!
From 0: [4, 240] → length 2
From 1: [4, 8, 240] → length 3 ← BEST!
From 2: [10, 240] → length 2
Understanding The Final Answer
After processing all elements:
dp = [1, 2, 1, 3]
[4, 8,10,240]
parent = [-1, 0, -1, 1]
Find maximum length:
max(dp) = 3 at index 3
Now reconstruct the chain:
Start at index 3 (value 240)
Step 1: At index 3
Value: 240
Parent: parent[3] = 1
Add 240 to result: [240]
Step 2: Go to parent, index 1
Value: 8
Parent: parent[1] = 0
Add 8 to result: [240, 8]
Step 3: Go to parent, index 0
Value: 4
Parent: parent[0] = -1 (STOP!)
Add 4 to result: [240, 8, 4]
Step 4: We went backwards, so reverse!
Final result: [4, 8, 240] ✓
This is our answer! 🎉
Why This Approach Works
The key insights:
1. SORTING first:
Allows us to build chains from small to large
Ensures we only check divisibility in one direction
2. DP ARRAY tracks length:
dp[i] = best chain length ENDING at position i
3. PARENT ARRAY tracks path:
parent[i] = where did this chain come from?
Allows reconstruction at the end
4. GREEDY CHOICE when extending:
When checking position i, try extending from ALL j < i
Pick the j that gives LONGEST chain!
5. RECONSTRUCTION walks backwards:
Start at best position
Follow parent pointers
Reverse at end (because we went backwards)
Beautiful! ✓
🔴 Approach 1: Brute Force - Understanding Every Possibility
The Naive Idea
Simplest approach: Try EVERY possible subset!
For nums = [1, 2, 4]:
All possible subsets:
[] (empty)
[1]
[2]
[4]
[1, 2]
[1, 4]
[2, 4]
[1, 2, 4]
Total: 2^3 = 8 subsets
For each subset:
Check if ALL pairs divide
Track the largest valid subset
Return the largest! ✓
How To Generate All Subsets?
We can use BIT MANIPULATION!
For array of size n, there are 2^n subsets.
Each subset can be represented by a binary number!
Example: nums = [1, 2, 4]
indices: 0, 1, 2
Binary 000 (0) → no elements → []
Binary 001 (1) → index 0 → [1]
Binary 010 (2) → index 1 → [2]
Binary 011 (3) → indices 0,1 → [1, 2]
Binary 100 (4) → index 2 → [4]
Binary 101 (5) → indices 0,2 → [1, 4]
Binary 110 (6) → indices 1,2 → [2, 4]
Binary 111 (7) → indices 0,1,2 → [1, 2, 4]
For each bit:
If bit is 1 → include that element
If bit is 0 → skip that element
This is the TRICK! 🔑
Step By Step Example
nums = [1, 2, 3]
Let's check all subsets:
mask = 0 (binary 000):
No elements selected → []
Valid? Yes (no pairs to check)
Size: 0
mask = 1 (binary 001):
Index 0 selected → [1]
Valid? Yes
Size: 1
mask = 2 (binary 010):
Index 1 selected → [2]
Valid? Yes
Size: 1
mask = 3 (binary 011):
Indices 0,1 selected → [1, 2]
Check pair (1,2): 2%1=0 ✓
Valid? Yes
Size: 2 ← Current best!
mask = 4 (binary 100):
Index 2 selected → [3]
Valid? Yes
Size: 1
mask = 5 (binary 101):
Indices 0,2 selected → [1, 3]
Check pair (1,3): 3%1=0 ✓
Valid? Yes
Size: 2 (same as best)
mask = 6 (binary 110):
Indices 1,2 selected → [2, 3]
Check pair (2,3): 3%2=1 ✗, 2%3=0 ✗
Valid? NO!
mask = 7 (binary 111):
All selected → [1, 2, 3]
Check pairs:
(1,2): 2%1=0 ✓
(1,3): 3%1=0 ✓
(2,3): 3%2=1 ✗, 2%3=0 ✗
Valid? NO!
Best valid subset: [1,2] or [1,3] with size 2 ✓
Complete Implementation
class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
int n = nums.length;
List<Integer> result = new ArrayList<>();
int maxSize = 0;
// Try all 2^n subsets
for (int mask = 0; mask < (1 << n); mask++) {
// Get subset for this mask
List<Integer> subset = getSubset(nums, mask);
// Check if this subset is valid
if (isValidSubset(subset)) {
// Track largest valid subset
if (subset.size() > maxSize) {
maxSize = subset.size();
result = new ArrayList<>(subset);
}
}
}
return result;
}
// Extract subset based on bit mask
private List<Integer> getSubset(int[] nums, int mask) {
List<Integer> subset = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
// Check if i-th bit is set
if ((mask & (1 << i)) != 0) {
subset.add(nums[i]);
}
}
return subset;
}
// Check if every pair in subset divides
private boolean isValidSubset(List<Integer> subset) {
int size = subset.size();
// Check all pairs
for (int i = 0; i < size; i++) {
for (int j = i + 1; j < size; j++) {
int a = subset.get(i);
int b = subset.get(j);
// Check if at least one direction divides
if (a % b != 0 && b % a != 0) {
return false;
}
}
}
return true;
}
}
Understanding The Bit Operations
Let's break down: (mask & (1 << i)) != 0
Example: mask = 5, i = 0
Step 1: (1 << i)
1 << 0 = 1 (binary: 001)
Step 2: mask & (1 << i)
mask = 5 (binary: 101)
1 << 0 = 1 (binary: 001)
101 & 001 = 001 = 1
Step 3: != 0?
1 != 0 → TRUE
So include index 0! ✓
Example: mask = 5, i = 1
Step 1: (1 << i)
1 << 1 = 2 (binary: 010)
Step 2: mask & (1 << i)
mask = 5 (binary: 101)
1 << 1 = 2 (binary: 010)
101 & 010 = 000 = 0
Step 3: != 0?
0 != 0 → FALSE
So skip index 1! ✓
This checks if a specific bit is set! 🔑
Why This Is Too Slow
TIME COMPLEXITY:
Generate all subsets: 2^n iterations
For each subset of size k:
Check all pairs: k × (k-1) / 2 pairs
Average k ≈ n/2
So approximately n²/4 checks per subset
Total: O(2^n × n²) ❌
For n = 20:
2^20 = 1,048,576 subsets
Each checks ~100 pairs
Total: ~100 million operations! ❌
For n = 1000 (max constraint):
2^1000 = IMPOSSIBLE! ❌
This would take longer than the age of the universe!
SPACE COMPLEXITY:
Storing subsets: O(n)
Verdict: Works for small n (≤15), but FAILS for large n! ❌
We need a MUCH better approach! 🔑
🟡 Approach 2: DP with Reconstruction (Optimal Solution)
The Complete Algorithm
Step 1: SORT the array
This enables the chain property!
Step 2: Build DP arrays
dp[i] = length of largest subset ending at i
parent[i] = previous index in the chain
Step 3: Find maximum length and its index
maxLen = max(dp)
maxIndex = index where dp is maximum
Step 4: Reconstruct the subset
Walk backwards using parent array
Build the actual subset
Let's implement this! ✓
Detailed Example Walkthrough
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
EXAMPLE 1: Multiple Competing Chains
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
nums = [4, 8, 10, 240]
This is interesting because:
- 240 is divisible by multiple previous numbers
- Multiple paths of different lengths
- Shows how DP picks the LONGEST chain
STEP 1: Sort
Already sorted: [4, 8, 10, 240]
STEP 2: Build DP arrays
Initialize:
dp = [1, 1, 1, 1]
parent = [-1, -1, -1, -1]
i=0 (value 4):
No previous elements
dp[0] = 1
parent[0] = -1
i=1 (value 8):
Check j=0 (value 4):
8 % 4 = 0 ✓
dp[1] = max(1, dp[0] + 1) = 2
parent[1] = 0
Chain so far: [4, 8]
Result: dp[1] = 2, parent[1] = 0
i=2 (value 10):
Check j=0 (value 4):
10 % 4 = 2 ✗
Check j=1 (value 8):
10 % 8 = 2 ✗
Result: dp[2] = 1, parent[2] = -1
Note: 10 doesn't divide by anything! Stands alone!
i=3 (value 240):
Check j=0 (value 4):
240 % 4 = 0 ✓
Can extend: dp[0] + 1 = 2
Potential chain: [4, 240]
Check j=1 (value 8):
240 % 8 = 0 ✓
Can extend: dp[1] + 1 = 3 ← Better!
Potential chain: [4, 8, 240]
Check j=2 (value 10):
240 % 10 = 0 ✓
Can extend: dp[2] + 1 = 2
Potential chain: [10, 240]
Best option: Extend from j=1 (length 3)
dp[3] = 3
parent[3] = 1
WHY? Because dp[1]=2 gives us chain [4,8]
Adding 240 gives [4,8,240] with length 3!
Final arrays:
dp = [1, 2, 1, 3]
parent = [-1, 0, -1, 1]
Visual of chains:
Index 0: [4] (length 1)
Index 1: [4, 8] (length 2)
Index 2: [10] (length 1, isolated)
Index 3: [4, 8, 240] (length 3) ← Winner!
STEP 3: Find maximum
maxLen = 3 at index 3
STEP 4: Reconstruct
Start at index 3 (value 240)
parent[3] = 1 → index 1 (value 8)
parent[1] = 0 → index 0 (value 4)
parent[0] = -1 → stop
Path: 3 → 1 → 0
Values: 240 → 8 → 4
Reverse: [4, 8, 240] ✓
KEY INSIGHT: Even though 240 divides by 4, 10, and 8,
we chose 8 because it had the LONGEST chain! 🔑
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
EXAMPLE 2: Tricky Multiple Paths
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
nums = [1, 2, 4, 8, 3, 9, 27, 81]
This has TWO separate chains:
Chain A: Powers of 2 → [1, 2, 4, 8]
Chain B: Powers of 3 → [1, 3, 9, 27, 81]
Which will DP choose?
STEP 1: Sort
[1, 2, 3, 4, 8, 9, 27, 81]
STEP 2: Build DP (let me show just key steps)
i=0 (1): dp[0]=1, parent[0]=-1
i=1 (2):
2%1=0 ✓ → dp[1]=2, parent[1]=0
Chain: [1,2]
i=2 (3):
3%1=0 ✓ → dp[2]=2, parent[2]=0
3%2=1 ✗
Chain: [1,3]
i=3 (4):
4%1=0 ✓ → length=2
4%2=0 ✓ → length=3 ← Best!
4%3=1 ✗
dp[3]=3, parent[3]=1
Chain: [1,2,4]
i=4 (8):
8%1=0 ✓ → length=2
8%2=0 ✓ → length=3
8%3=2 ✗
8%4=0 ✓ → length=4 ← Best!
dp[4]=4, parent[4]=3
Chain: [1,2,4,8]
i=5 (9):
9%1=0 ✓ → length=2
9%2=1 ✗
9%3=0 ✓ → length=3 ← Best!
9%4=1 ✗
9%8=1 ✗
dp[5]=3, parent[5]=2
Chain: [1,3,9]
i=6 (27):
27%1=0 ✓ → length=2
27%2=1 ✗
27%3=0 ✓ → length=3
27%4=3 ✗
27%8=3 ✗
27%9=0 ✓ → length=4 ← Best!
dp[6]=4, parent[6]=5
Chain: [1,3,9,27]
i=7 (81):
81%1=0 ✓ → length=2
81%2=1 ✗
81%3=0 ✓ → length=3
81%4=1 ✗
81%8=1 ✗
81%9=0 ✓ → length=4
81%27=0 ✓ → length=5 ← Best!
dp[7]=5, parent[7]=6
Chain: [1,3,9,27,81]
Final arrays:
dp = [1, 2, 2, 3, 4, 3, 4, 5]
[1, 2, 3, 4, 8, 9,27,81]
parent = [-1, 0, 0, 1, 3, 2, 5, 6]
STEP 3: Find maximum
maxLen = 5 at index 7
STEP 4: Reconstruct
7 → 6 → 5 → 2 → 0
81 → 27 → 9 → 3 → 1
Result: [1, 3, 9, 27, 81] ✓
KEY INSIGHT: Powers of 3 chain (length 5) beats
powers of 2 chain (length 4)! 🔑
Visual comparison:
Chain A: [1, 2, 4, 8] → length 4
Chain B: [1, 3, 9, 27, 81] → length 5 ← Winner!
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
EXAMPLE 3: The Divisibility Web
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
nums = [1, 2, 4, 8, 16, 32, 64]
Perfect chain of powers of 2!
Each divides the next!
After sort: [1, 2, 4, 8, 16, 32, 64]
DP building:
i=0 (1): dp[0]=1
i=1 (2): 2%1=0 → dp[1]=2, parent[1]=0
i=2 (4): 4%2=0 → dp[2]=3, parent[2]=1
i=3 (8): 8%4=0 → dp[3]=4, parent[3]=2
i=4 (16): 16%8=0 → dp[4]=5, parent[4]=3
i=5 (32): 32%16=0 → dp[5]=6, parent[5]=4
i=6 (64): 64%32=0 → dp[6]=7, parent[6]=5
Final:
dp = [1, 2, 3, 4, 5, 6, 7]
parent = [-1, 0, 1, 2, 3, 4, 5]
Perfect chain!
Result: [1, 2, 4, 8, 16, 32, 64] ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
EXAMPLE 4: The Diamond Pattern (Most Interesting!)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
nums = [1, 2, 3, 6, 12, 36]
This creates a DIAMOND of divisibility:
1
/ \
2 3
\ /
6
|
12
|
36
After sort: [1, 2, 3, 6, 12, 36]
i=0 (1): dp[0]=1, parent[0]=-1
i=1 (2):
2%1=0 ✓ → dp[1]=2, parent[1]=0
i=2 (3):
3%1=0 ✓ → dp[2]=2, parent[2]=0
3%2=1 ✗
i=3 (6):
6%1=0 ✓ → length=2
6%2=0 ✓ → length=3 (chain: [1,2,6])
6%3=0 ✓ → length=3 (chain: [1,3,6])
Ties! Let's say we choose j=1 (first found)
dp[3]=3, parent[3]=1
i=4 (12):
12%1=0 ✓ → length=2
12%2=0 ✓ → length=3
12%3=0 ✓ → length=3
12%6=0 ✓ → length=4 ← Best!
dp[4]=4, parent[4]=3
i=5 (36):
36%1=0 ✓ → length=2
36%2=0 ✓ → length=3
36%3=0 ✓ → length=3
36%6=0 ✓ → length=4
36%12=0 ✓ → length=5 ← Best!
dp[5]=5, parent[5]=4
Final:
dp = [1, 2, 2, 3, 4, 5]
parent = [-1, 0, 0, 1, 3, 4]
Reconstruction:
5 → 4 → 3 → 1 → 0
36 → 12 → 6 → 2 → 1
Result: [1, 2, 6, 12, 36] ✓
Note: Could also be [1, 3, 6, 12, 36] (same length)
but DP chose path through 2 first!
Visual of the path chosen:
1 → 2 → 6 → 12 → 36
The diamond allowed multiple paths,
but DP efficiently found the longest! 🔑
Complete Implementation
class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
int n = nums.length;
// Step 1: Sort the array
Arrays.sort(nums);
// Step 2: Build DP arrays
int[] dp = new int[n];
int[] parent = new int[n];
// Initialize
Arrays.fill(dp, 1);
Arrays.fill(parent, -1);
int maxLen = 1;
int maxIndex = 0;
// Fill DP arrays
for (int i = 1; i < n; i++) {
for (int 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;
}
}
}
// Track maximum
if (dp[i] > maxLen) {
maxLen = dp[i];
maxIndex = i;
}
}
// Step 3 & 4: Reconstruct the subset
List<Integer> result = new ArrayList<>();
int current = maxIndex;
while (current != -1) {
result.add(nums[current]);
current = parent[current];
}
// Reverse to get correct order
Collections.reverse(result);
return result;
}
}
🔍 Detailed Edge Cases and Tricky Scenarios
Edge Case 1: All Prime Numbers (No Chains)
nums = [2, 3, 5, 7, 11, 13]
All prime numbers - no divisibility between them!
Only divisor is 1, but 1 is not in the array!
After sort: [2, 3, 5, 7, 11, 13]
DP building:
i=0 (2): dp[0]=1, parent[0]=-1
i=1 (3): 3%2=1 ✗ → dp[1]=1, parent[1]=-1
i=2 (5): 5%2=1 ✗, 5%3=2 ✗ → dp[2]=1, parent[2]=-1
...
All elements: dp[i]=1, parent[i]=-1
All have length 1!
Result: [2] (or any single prime) ✓
KEY: When no divisibility, each element is its own subset!
Edge Case 2: Factorials (Dense Divisibility)
nums = [1, 2, 6, 24, 120, 720]
These are factorials: 1!, 2!, 3!, 4!, 5!, 6!
Each factorial divides all subsequent ones!
After sort: [1, 2, 6, 24, 120, 720]
Why this is special:
2 = 2×1
6 = 3×2
24 = 4×6
120 = 5×24
720 = 6×120
Perfect chain!
DP building:
i=0 (1): dp[0]=1
i=1 (2): 2%1=0 ✓ → dp[1]=2, parent[1]=0
i=2 (6): 6%2=0 ✓ → dp[2]=3, parent[2]=1
i=3 (24): 24%6=0 ✓ → dp[3]=4, parent[3]=2
i=4 (120): 120%24=0 ✓ → dp[4]=5, parent[4]=3
i=5 (720): 720%120=0 ✓ → dp[5]=6, parent[5]=4
Result: [1, 2, 6, 24, 120, 720] - entire array! ✓
KEY: Factorial sequences form perfect chains!
Edge Case 3: Mixed Bases (2s and 3s competing)
nums = [2, 4, 8, 16, 3, 9, 27]
Two competing exponential chains:
Powers of 2: [2, 4, 8, 16]
Powers of 3: [3, 9, 27]
After sort: [2, 3, 4, 8, 9, 16, 27]
DP building:
i=0 (2): dp[0]=1
i=1 (3): 3%2=1 ✗ → dp[1]=1
i=2 (4): 4%2=0 ✓ → dp[2]=2, parent[2]=0
i=3 (8): 8%4=0 ✓ → dp[3]=3, parent[3]=2
i=4 (9): 9%3=0 ✓ → dp[4]=2, parent[4]=1
i=5 (16): 16%8=0 ✓ → dp[5]=4, parent[5]=3
i=6 (27): 27%9=0 ✓ → dp[6]=3, parent[6]=4
Final dp: [1, 1, 2, 3, 2, 4, 3]
[2, 3, 4, 8, 9,16,27]
Maximum: length=4 at index 5
Reconstruction: 16 → 8 → 4 → 2
Result: [2, 4, 8, 16] ✓
Powers of 2 wins! (length 4 vs 3)
KEY: When multiple chains compete, longest wins!
Edge Case 4: The LCM Trap
nums = [2, 3, 6, 12, 18]
Tricky because:
6 = LCM(2,3)
12 = LCM(6,2) = LCM(2,3,6)
18 = LCM(6,3)
After sort: [2, 3, 6, 12, 18]
DP building:
i=0 (2): dp[0]=1, parent[0]=-1
i=1 (3):
3%2=1 ✗
dp[1]=1, parent[1]=-1
i=2 (6):
6%2=0 ✓ → length=2
6%3=0 ✓ → length=2
Both equal! Choose first: j=0
dp[2]=2, parent[2]=0
i=3 (12):
12%2=0 ✓ → length=2
12%3=0 ✓ → length=2
12%6=0 ✓ → length=3 ← Best!
dp[3]=3, parent[3]=2
i=4 (18):
18%2=0 ✓ → length=2
18%3=0 ✓ → length=2
18%6=0 ✓ → length=3
18%12=6 ✗
dp[4]=3, parent[4]=2
Final dp: [1, 1, 2, 3, 3]
[2, 3, 6,12,18]
Two subsets with length 3:
Path from 12: 12 → 6 → 2 = [2, 6, 12]
Path from 18: 18 → 6 → 2 = [2, 6, 18]
Algorithm returns first found: [2, 6, 12] ✓
KEY: Multiple equal-length subsets possible!
Algorithm returns one (not necessarily all)!
Edge Case 5: The Single Large Multiple
nums = [2, 3, 5, 7, 210]
210 = 2 × 3 × 5 × 7 (divides by all others!)
After sort: [2, 3, 5, 7, 210]
DP building:
i=0 (2): dp[0]=1
i=1 (3): 3%2=1 ✗ → dp[1]=1
i=2 (5): 5%2=1 ✗, 5%3=2 ✗ → dp[2]=1
i=3 (7): No divisibility → dp[3]=1
i=4 (210):
210%2=0 ✓ → length=2
210%3=0 ✓ → length=2
210%5=0 ✓ → length=2
210%7=0 ✓ → length=2
All equal! Choose first: j=0
dp[4]=2, parent[4]=0
Result: [2, 210] ✓
But wait! Why not longer chain?
Because 2,3,5,7 don't divide each other!
Only 210 divides by them!
We can't have [2, 3, 210] because 3 doesn't divide 2!
We can't have [3, 5, 210] because 5 doesn't divide 3!
Maximum possible: length 2
Any pair [x, 210] where x ∈ {2,3,5,7}
KEY: Even with common multiple, need chain property!
Each element must divide the NEXT one!
Edge Case 6: Large Numbers with Hidden Pattern
nums = [1, 7, 49, 343, 2401]
These are powers of 7: 7^0, 7^1, 7^2, 7^3, 7^4
After sort: [1, 7, 49, 343, 2401]
DP building:
i=0 (1): dp[0]=1
i=1 (7): 7%1=0 ✓ → dp[1]=2, parent[1]=0
i=2 (49): 49%7=0 ✓ → dp[2]=3, parent[2]=1
i=3 (343): 343%49=0 ✓ → dp[3]=4, parent[3]=2
i=4 (2401): 2401%343=0 ✓ → dp[4]=5, parent[4]=3
Perfect chain!
Result: [1, 7, 49, 343, 2401] ✓
KEY: Powers of any prime form perfect divisible chains!
Edge Case 7: The Interleaved Chains
nums = [1, 2, 3, 4, 6, 8, 12, 24]
This has multiple interleaved chains:
Chain A: 1 → 2 → 4 → 8 (powers of 2)
Chain B: 1 → 2 → 6 → 12 → 24 (path through 6)
Chain C: 1 → 3 → 6 → 12 → 24 (path through 3)
After sort: [1, 2, 3, 4, 6, 8, 12, 24]
DP building (showing key steps):
i=0 (1): dp[0]=1
i=1 (2): dp[1]=2, parent[1]=0
i=2 (3): dp[2]=2, parent[2]=0
i=3 (4): dp[3]=3, parent[3]=1 (from 2)
i=4 (6):
6%2=0 → length=3
6%3=0 → length=3
Choose first: dp[4]=3, parent[4]=1
i=5 (8): dp[5]=4, parent[5]=3 (from 4)
i=6 (12):
12%4=0 → length=4
12%6=0 → length=4
12%8=4 ✗
Choose first: dp[6]=4, parent[6]=3
i=7 (24):
24%4=0 → length=4
24%6=0 → length=4
24%8=0 → length=5 ← Best!
24%12=0 → length=5 (tied)
Choose first best: dp[7]=5, parent[7]=5
Result: [1, 2, 4, 8, 24] ✓
Alternative equal-length path:
[1, 2, 6, 12, 24] also length 5!
KEY: When multiple paths have same length,
algorithm returns first found (depends on loop order)!
📊 Complexity Analysis
Time Complexity
STEP 1: Sorting
O(n log n)
STEP 2: Building DP
Outer loop: n iterations
Inner loop: up to n iterations
Each check: O(1) modulo operation
Total: O(n²)
STEP 3: Finding maximum
O(n) single pass
STEP 4: Reconstruction
O(k) where k = length of result
At most O(n)
Overall: O(n log n) + O(n²) + O(n) + O(n)
= O(n²) ✓
For n = 1000 (max constraint):
1,000,000 operations
Very fast! ✓
Space Complexity
Arrays:
dp array: O(n)
parent array: O(n)
result list: O(n) in worst case
Sorting: O(log n) stack space
Total: O(n) ✓
Efficient! ✓
🎯 Pattern Recognition
The LIS Variant Family
CORE LIS PATTERN:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
1. Sort if needed
2. For each i, check all j < i
3. If condition met, extend sequence
4. Track maximum
VARIANTS:
Problem 247: Longest Increasing Subsequence
Condition: nums[j] < nums[i]
Return: Length only
Problem 248: Increasing Triplet
Condition: nums[j] < nums[i]
Return: Boolean (exists or not)
Optimization: Two variables for k=3
Problem 249: Largest Divisible Subset
Condition: nums[i] % nums[j] == 0
Return: Actual subset elements
New: Need reconstruction!
Common structure:
- DP with O(n²) time
- Check previous elements
- Extend if condition met
- Track maximum length
New skill: PATH RECONSTRUCTION! 🔑
When To Use Reconstruction
WHEN YOU NEED:
✓ The actual elements (not just count)
✓ The actual path (not just length)
✓ The actual configuration
TECHNIQUE:
1. Add parent/previous array
parent[i] = j means "i came from j"
2. During DP, track WHERE we came from
When updating dp[i], save parent[i] = j
3. After DP, walk backwards
current → parent[current] → parent[parent[current]] → ...
4. Build result and reverse
(Because we walked backwards!)
This adds O(n) space but same time complexity! ✓
Divisibility Properties To Remember
KEY PROPERTIES:
1. TRANSITIVITY:
If a|b AND b|c, then a|c
(| means "divides")
This is why sorting works!
We only check consecutive pairs in sorted order!
2. CHAIN PROPERTY:
In sorted divisible subset [a, b, c]:
If b%a=0 AND c%b=0
Then automatically c%a=0
No need to check all pairs! ✓
3. GCD CONNECTION:
If gcd(a,b)=a, then a|b
But we don't need GCD for this problem!
Direct modulo is simpler!
4. REFLEXIVE:
Every number divides itself: a%a=0
This is why dp[i] starts at 1!
💻 Complete Working Code
class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
int n = nums.length;
// Step 1: Sort the array
Arrays.sort(nums);
// Step 2: Build DP arrays
int[] dp = new int[n]; // Length of longest subset ending at i
int[] parent = new int[n]; // Previous index in the chain
// Initialize
Arrays.fill(dp, 1);
Arrays.fill(parent, -1);
int maxLen = 1;
int maxIndex = 0;
// Fill DP arrays
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
// Check divisibility
if (nums[i] % nums[j] == 0) {
// Can extend subset ending at j
if (dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
parent[i] = j; // Track where we came from
}
}
}
// Track maximum length and index
if (dp[i] > maxLen) {
maxLen = dp[i];
maxIndex = i;
}
}
// Step 3: Reconstruct the subset
List<Integer> result = new ArrayList<>();
int current = maxIndex;
// Walk backwards using parent array
while (current != -1) {
result.add(nums[current]);
current = parent[current];
}
// Reverse to get correct order (smallest to largest)
Collections.reverse(result);
return result;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.largestDivisibleSubset(new int[] {1, 2, 3}));
// Output: [1, 2] or [1, 3]
System.out.println(sol.largestDivisibleSubset(new int[] {1, 2, 4, 8}));
// Output: [1, 2, 4, 8]
System.out.println(sol.largestDivisibleSubset(new int[] {1, 2, 4, 3, 6, 12}));
// Output: [1, 3, 6, 12] or [1, 2, 4, 12]
}
}
🔑 Key Insights Summary
The Learning Journey
CRAWL (Understanding):
✓ What is divisible subset?
✓ Understanding every-pair requirement
✓ Why sorting helps (transitivity!)
✓ Connection to LIS pattern
WALK (Building):
✓ DP state definition
✓ Why we need parent array
✓ Building DP step by step
✓ Understanding reconstruction
RUN (Mastery):
✓ Complete implementation
✓ Path reconstruction technique
✓ Edge cases analysis
✓ Divisibility properties
✓ Pattern recognition
Natural baby-to-expert progression! 🎯
The Core Understanding
1. WHY sort first?
Enables chain property!
Transitivity of divisibility!
2. WHAT is dp[i]?
Length of largest subset ENDING at i
Same as LIS! ✓
3. HOW to track elements?
Use parent array!
parent[i] = previous index in chain
4. WHEN to update parent?
When we find better dp[i]
Save j as parent[i]
5. WHERE to reconstruct?
Walk backwards from maxIndex
Build result by following parents! 🔑
Mental Model
Think of it as CHAIN BUILDING:
nums = [1, 2, 4, 8]
Chain 1: 1 (length 1)
↓
Chain 2: 1 → 2 (length 2)
↓
Chain 3: 1 → 2 → 4 (length 3)
↓
Chain 4: 1 → 2 → 4 → 8 (length 4)
Each arrow is recorded in parent array:
parent[1] = 0 (2 came from 1)
parent[2] = 1 (4 came from 2)
parent[3] = 2 (8 came from 4)
Walk backwards to reconstruct:
8 → 4 → 2 → 1 ✓
📝 Quick Revision
🎯 Core Concept
Divisible subset = LIS variant with divisibility
Sorting + Transitivity = Only check consecutive
Parent array = Track path for reconstruction
⚡ Algorithm Steps
1. Sort array
2. Build DP:
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
3. Find max index
4. Reconstruct:
while current != -1:
result.add(nums[current])
current = parent[current]
reverse result
Quick Implementation
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class Solution {
public List<Integer> largestDivisibleSubset(int[] a) {
Arrays.sort(a);
// return recursive(a);
return dp(a);
}
private List<Integer> dp(int[] a) {
// This approach is similar to LIS DP approach.
int len = a.length;
// Step 1: initialize 2 arrays, dp and parent
int[] dp = new int[len];
Arrays.fill(dp, 1);
int[] parent = new int[len];
Arrays.fill(parent, -1);
// Step 2: same as LIS with just change in condition
for (int i = 1; i < len; i++) {
for (int j = 0; j < i; j++) {
// not only mod, only update when its max.
if (a[i] % a[j] == 0 && dp[i] < 1 + dp[j]) {
dp[i] = 1 + dp[j];
// where it came from - linking to create the result.
parent[i] = j;
}
}
}
// Step 3: find max in DP where we get largest divisible set
int index = 0;
int currMax = dp[0];
for (int i = 1; i < len; i++) {
if (dp[i] > currMax) {
currMax = dp[i];
index = i;
}
}
// Step 4: traceback the result
List<Integer> res = new ArrayList<>();
res.add(a[index]);
while (parent[index] != -1) {
index = parent[index];
res.add(a[index]);
}
Collections.reverse(res);
return res;
}
private List<Integer> recursive(int[] a) {
// Step 1: get subsets of array
// [1,2,3] => {},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3} => 8 subsets
// Think of bit manipulation: 000 to 111
// 000 => {} and 111 => {1,2,3} and 101 => {1,3}
// How many subsets? 2^(a.len): 2^3 = 8
// In binary format, 8 is 1000 which can be obtained by (1 << a.len)
// and we need to generate all binary represenations from 000 to 111
// and get indices where bits are set and take those numbers.
// For example, 101 => take numbers 1 and 3
int len = a.length;
List<Integer> res = new ArrayList<>();
int currSize = Integer.MIN_VALUE;
for (int mask = 0; mask < (1 << len); mask++) {
// Lets say mask is 5 (101), we need to get {1,3}
List<Integer> subset = getSubset(a, mask);
if (isValid(subset) && currSize < subset.size()) {
res = new ArrayList<>(subset);
currSize = subset.size();
}
}
return res;
}
private boolean isValid(List<Integer> list) {
// Another important property is transitive divisibility property
// Since the array is sorted and if we get any subset like (4,8,240), we
// actually need to check every pair if it satisfies the condition like
// 8%4 and 240%4 and 240%8.
// Due to sorting property, we just need to check adjacent numbers.
// for(a,b,c), if b%a=0 and c%b=0, its c%a=0
int size = list.size();
for (int i = 1; i < size; i++) {
if (list.get(i) % list.get(i - 1) != 0) {
return false;
}
}
return true;
}
private List<Integer> getSubset(int[] a, int mask) {
List<Integer> subset = new ArrayList<>();
// Lets say we received mask as 5 (101)
// we need to put numbers at indices 0 and 2 (bits set) in the subset
// Below for loop runs 3 times: 101 & 001, 101 & 010, 101 & 100 which gives 1,0
// and 1 which means take numbers at indices 0 and 2
int len = a.length;
for (int i = 0; i < len; i++) {
if ((mask & (1 << i)) != 0) {
subset.add(a[i]);
}
}
return subset;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.largestDivisibleSubset(new int[] { 1, 2, 4, 8 }).equals(List.of(1, 2, 4, 8)));
System.out.println(s.largestDivisibleSubset(new int[] { 4, 8, 10, 240 }).equals(List.of(4, 8, 240)));
}
}
🔑 Key Patterns
DP building:
- Check all previous j < i
- If divisible, can extend
- Track parent for reconstruction
Reconstruction:
- Start at maxIndex
- Follow parent pointers
- Reverse at end
🎪 Memory Aid
"Sort first, chain forms"
"Parent tracks the path"
"Walk back to build result"
Complexity: O(n²) time, O(n) space
🎉 Congratulations!
You've mastered through baby steps: - ✅ CRAWL: Understanding divisibility property - ✅ WALK: Building DP with parent tracking - ✅ RUN: Complete reconstruction technique - ✅ Transitivity proof included - ✅ Why sorting is essential - ✅ All edge cases covered - ✅ Path reconstruction mastered - ✅ True comprehensive understanding
You've learned a NEW SKILL: Path Reconstruction in DP with textbook-style learning! 🚀✨
KEY TAKEAWAY: When you need actual elements (not just count), add parent array to track WHERE each state came from, then walk backwards to reconstruct! 🔑