Largest Divisible Subset

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, or
• answer[j] % answer[i] == 0

If there are multiple solutions, return any of them.

OR

Given a set of distinct positive integers, find the largest subset such that every pair of elements in the subset (i, j) satisfies either i % j = 0 or j % i = 0.

Examples

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

• All the integers in nums are unique.

Solution

Method 1 - Use DP and Longest Increasing Subsequence

We know that for two numbers a and b, a % b == 0 if a >= b. Now lets see how to convert the problem to Longest Increasing Subsequence (LIS).

Let's consider the example [1, 2, 3, 6]:

• Start with the smallest number: 2 % 1 == 0 is true, so we can form the subset {1, 2}.
• Continue with the next number: 3 % 1 == 0 is true, so we can form another subset {1, 3}.
• For the number 6, 6 % 2 == 0 gives us a subset {1, 2, 6} and 6 % 3 == 0 gives {1, 3, 6}.

While creating these subsets, note that 2 and 3 do not belong to the same subset. Our implementation handles this during the construction of the subsets.

Also, in example our list was sorted but if it is not sorted, we may have to do 2 mod operations => a%b == 0 and b%a == 0. So, when the array is sorted, than we can just to b%a==0 provided b comes after a. So, sorting the array is not prerequisite, but helps.

Algo

1. Sort nums.
2. Find size of longest divisible subset LDS through the same approach as in LIS
3. Construct LDS by iterating through dp from right to left

Code

Java

public class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        var dp = new int[nums.length];
        int ldsSize = getLDSSize(nums, dp);
        return constructLDS(nums, dp, ldsSize);
    }

    private int getLDSSize(int[] nums, int[] dp) {
        Arrays.sort(nums);
        Arrays.fill(dp, 1);
        var ldsSize = 1;

        for (var i = 1; i < nums.length; i++) {
            for (var j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                    ldsSize = Math.max(ldsSize, dp[i]);
                }
            }
        }
        return ldsSize;
    }

    private List<Integer> constructLDS(int[] nums, int[] dp, int ldsSize) {
        var prev = -1;
        var lds = new LinkedList<Integer>();
        // iterate from end of array
        for (var i = dp.length - 1; i >= 0; i--) {
            if (dp[i] == ldsSize && (prev == -1 || prev % nums[i] == 0)) {
                lds.addFirst(nums[i]);
                ldsSize--;
                prev = nums[i];
            }
        }
        return lds;
    }
}

Python

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        def getLDSSize(nums: List[int], dp: List[int]) -> int:
            nums.sort()
            dp[:] = [1] * len(nums)
            lds_size = 1
            
            for i in range(1, len(nums)):
                for j in range(i):
                    if nums[i] % nums[j] == 0:
                        dp[i] = max(dp[i], dp[j] + 1)
                        lds_size = max(lds_size, dp[i])
                        
            return lds_size
        
        def constructLDS(nums: List[int], dp: List[int], lds_size: int) -> List[int]:
            prev = -1
            lds: deque[int] = deque()
            for i in range(len(dp) - 1, -1, -1):
                if dp[i] == lds_size and (prev == -1 or prev % nums[i] == 0):
                    lds.appendleft(nums[i])
                    lds_size -= 1
                    prev = nums[i]
            return list(lds)
        
        if not nums:
            return []
        
        dp = [0] * len(nums)
        lds_size = getLDSSize(nums, dp)
        return constructLDS(nums, dp, lds_size)

Complexity

• ⏰ Time complexity: O(n^2)
• 🧺 Space complexity: O(n)

Method 2 - Using LIS but Combine Functions From Method 1

We can combine all the functions in Method 1 using prev array, storing indices of previous value when creating LIS. We also tracking max index so that we can construct result later.

Approach

1. Sort the Array: Sorting helps reduce redundant checks. If not sorted, we may have to check both conditions: a % b == 0 and b % a == 0.
2. Dynamic Programming Setup: Use two arrays: dp to keep track of the size of the largest divisible subset ending at each index, and prev to help reconstruct the subset.
3. Update Subset Lengths: Iterate through the sorted array and update dp and prev based on the divisibility condition.
4. Reconstruct the Subset: Using the prev array, reconstruct the largest subset and return it.

Code

Java

public class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        if (nums.length == 0) return new ArrayList<>();
        
        Arrays.sort(nums);
        int n = nums.length;
        int[] dp = new int[n];
        int[] prev = new int[n];
        Arrays.fill(dp, 1);
        Arrays.fill(prev, -1);
        
        int maxIdx = 0;
        
        for (int i = 0; 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;
                    prev[i] = j;
                }
            }
            if (dp[i] > dp[maxIdx]) {
                maxIdx = i;
            }
        }
        
        List<Integer> ans = new ArrayList<>();
        for (int i = maxIdx; i >= 0; i = prev[i]) {
            ans.add(nums[i]);
            if (prev[i] == -1) {
	            break;
	        }
        }
        
        return ans;
    }
}

Python

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        if not nums:
            return []
        
        nums.sort()
        n = len(nums)
        dp: List[int] = [1] * n
        prev: List[int] = [-1] * n
        max_idx: int = 0
        
        for i in range(n):
            for j in range(i):
                if nums[i] % nums[j] == 0 and dp[i] < dp[j] + 1:
                    dp[i] = dp[j] + 1
                    prev[i] = j
            
            if dp[i] > dp[max_idx]:
                max_idx = i
        
        ans: List[int] = []
        idx: int = max_idx
        while idx != -1:
            ans.append(nums[idx])
            idx = prev[idx]
        
        ans.reverse()
        return ans

Complexity

• ⏰ Time complexity: O(n^2), where n is the number of elements in nums.
• 🧺 Space complexity: O(n), due to the space used for the dynamic programming arrays.