368. Largest Divisible Subset

Time: O(n^2)

Space: O(n)

Intuition

Sort the array. dp[i] = length of the largest divisible subset ending at nums[i]. For nums[i] to extend subset dp[j], we need nums[i] % nums[j] == 0 (since sorted, nums[j] <= nums[i]). Track parent pointers to reconstruct the subset.

Algorithm

1Sort nums. dp[i]=1, parent[i]=-1.
2For i from 1 to n-1: for j from i-1 to 0: if nums[i]%nums[j]==0 and dp[j]+1>dp[i]: dp[i]=dp[j]+1, parent[i]=j.
3Find index of max dp value. Trace back using parent pointers.

Example Walkthrough

Input: nums = [1,2,3,6] -> sorted: [1,2,3,6]

1.dp[0]=1. dp[1]: 2%1==0 -> dp[1]=2. dp[2]: 3%1==0 -> dp[2]=2. dp[3]: 6%3==0 -> dp[3]=3.
2.Max at index 3, trace: 6<-3<-1.

Output: [1,3,6]

Common Pitfalls

•Only check divisibility in one direction since array is sorted - nums[i] % nums[j] (not nums[j] % nums[i]).

368.cs

// Approach: Sort the array so that for any valid pair (a, b) with a < b, b % a == 0.
// Define dp[i] = length of the largest divisible subset ending at nums[i].
// For each i, look back at all j < i: if nums[i] % nums[j] == 0, dp[i] = max(dp[i], dp[j] + 1).
// Also store a prev[i] index for path reconstruction.
// After filling dp, find the index with maximum dp value and backtrack via prev to recover the subset.
// Time: O(n^2) Space: O(n) for dp and prev arrays.

public class Solution
{
    public IList<int> LargestDivisibleSubset(int[] nums)
    {
        int n = nums.Length;
        List<int> ans = new List<int>();
        // sizeEndsAt[i] := the maximum size ends in nums[i]
        int[] sizeEndsAt = new int[n];
        // prevIndex[i] := the best index s.t.
        // 1. nums[i] % nums[prevIndex[i]] == 0 and
        // 2. can increase the size of the subset
        int[] prevIndex = new int[n];
        int maxSize = 0; // Max size of the subset
        int index = -1;  // Track the best ending index

        Array.Fill(sizeEndsAt, 1);
        Array.Fill(prevIndex, -1);
        Array.Sort(nums);

        // Fix the maximum ending number in the subset.
        for (int i = 0; i < n; ++i)
        {
            for (int j = i - 1; j >= 0; --j)
            {
                if (nums[i] % nums[j] == 0 && sizeEndsAt[i] < sizeEndsAt[j] + 1)
                {
                    sizeEndsAt[i] = sizeEndsAt[j] + 1;
                    prevIndex[i] = j;
                }
            }
            // Find a new subset that has a bigger size.
            if (maxSize < sizeEndsAt[i])
            {
                maxSize = sizeEndsAt[i];
                index = i; // Update the best ending index.
            }
        }

        // Loop from the back to the front.
        while (index != -1)
        {
            ans.Add(nums[index]);
            index = prevIndex[index];
        }

        return ans;
    }
}

Was this solution helpful?