Leetcode 368. Largest Divisible Subset

Jimmy   Apr 6, 2025   1302 words   ~35 mins
#Array #Math #Dynamic Programming #Sorting

Table of Contents

Problem Informations

Problem Description

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 \leq nums.length \leq 1000$
  • $1 \leq nums[i] \leq 2 \times 10^9$
  • All the integers in nums are unique.

Intuition

The problem requires finding the largest subset of a list of distinct positive integers such that every pair of numbers in the subset satisfies the condition of divisibility. The intuition is to sort the array first, which facilitates checking the divisibility condition because if a number is divisible by another, they must follow an increasing order. Dynamic programming is employed to efficiently compute the sizes of the largest divisible subsets ending at each index, allowing a solution that builds upon previously computed results for smaller indices.

Approach

  1. Sorting: Start by sorting the array. Sorting simplifies the problem as we only need to check divisibility on past numbers rather than having to check both directions.

  2. Dynamic Programming Preparation:

    • We initiate a dp array where dp[i] represents the size of the largest divisible subset ending at index i.
    • We also initialize a subsets vector of sets to keep track of the actual elements of the subset leading to the largest subset for each number.

  3. Initialize Each Number as a Singleton Subset:

    • Initially, each number forms a subset of itself, so dp[i] starts as 1 and each set in subsets starts with the corresponding number.

  4. Dynamic Programming Calculation:

    • For each number at index i, check all previous numbers (from index 0 to i-1).
    • If nums[i] is divisible by nums[j], attempt to extend the largest subset ending with nums[j] to include nums[i].
    • This involves checking if adding nums[i] to the subset ending at nums[j] results in a larger subset than currently recorded at dp[i].

  5. Subset Construction:

    • If a larger subset is found through a number, we update dp[i] and include elements from the corresponding subset in subsets[j] to subsets[i].
    • Maintain the index of the largest subset found during the iteration over all indices.

  6. Result Construction:

    • The largest subset is then directly retrieved from the subsets vector using the index of the largest subset computed.
    • Convert this set to a vector and return it as the result.

This algorithm leverages a combination of sorting, dynamic programming, and sets to efficiently find and store not only the sizes of the candidate subsets but also the elements themselves. The complexity is dominated by the need to traverse and compare subsets through the loop, leading to an overall time complexity of $O(n^2)$.

Code

C++

class Solution {

public:
    // Helper function to calculate the largest subset size ending at index 'idx'
    int calc(vector<int>& nums, vector<int>& dp, vector<set<int>>& subsets, int idx) {
        // Return already computed value if present
        if (dp[idx] != -1) {
            return dp[idx];
        }
        
        // Initialize current subset size to 1 (at least the number itself)
        dp[idx] = 1;
        int maxSubsetIdx = -1;

        // Find a previous number that nums[idx] can be divided by to form a larger subset
        for (int i = 0; i < idx; ++i) {
            if (nums[idx] % nums[i] == 0 && 
                (maxSubsetIdx == -1 || calc(nums, dp, subsets, maxSubsetIdx) < calc(nums, dp, subsets, i))) {
                maxSubsetIdx = i;
            }
        }
        
        // Update the current dp value if a larger subset was found
        if (maxSubsetIdx != -1) {
            dp[idx] += dp[maxSubsetIdx];
            subsets[idx].insert(subsets[maxSubsetIdx].begin(), subsets[maxSubsetIdx].end());
        }
        return dp[idx];
    }

    // Main function to find the largest divisible subset
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        int n = nums.size();
        
        // Sort the numbers to allow easy subset checking
        sort(nums.begin(), nums.end());
        
        // Initialize DP and subsets array
        vector<int> dp(n, -1);
        vector<set<int>> subsets(n);

        // Initially each number forms a singleton subset
        for (int i = 0; i < n; ++i) {
            subsets[i].insert(nums[i]);
        }

        int largestSubsetIdx = 0; // Index of largest subset found

        // Calculate largest subset for each number
        for (int i = 0; i < n; ++i) {
            if (calc(nums, dp, subsets, i) > dp[largestSubsetIdx]) {
                largestSubsetIdx = i;
            }
        }

        // Return the largest subset found
        return vector<int>(subsets[largestSubsetIdx].begin(), subsets[largestSubsetIdx].end());
    }
};

Python

class Solution:

    # Helper function to calculate the largest subset size ending at index 'idx'
    def calc(self, nums, dp, subsets, idx):
        # Return already computed value if present
        if dp[idx] != -1:
            return dp[idx]
        
        # Initialize current subset size to 1 (at least the number itself)
        dp[idx] = 1
        maxSubsetIdx = -1

        # Find a previous number that nums[idx] can be divided by to form a larger subset
        for i in range(idx):
            if nums[idx] % nums[i] == 0 and (
                maxSubsetIdx == -1 or self.calc(nums, dp, subsets, maxSubsetIdx) < self.calc(nums, dp, subsets, i)):
                maxSubsetIdx = i
        
        # Update the current dp value if a larger subset was found
        if maxSubsetIdx != -1:
            dp[idx] += dp[maxSubsetIdx]
            subsets[idx].update(subsets[maxSubsetIdx])
        return dp[idx]

    # Main function to find the largest divisible subset
    def largestDivisibleSubset(self, nums):
        n = len(nums)
        
        # Sort the numbers to allow easy subset checking
        nums.sort()
        
        # Initialize DP and subsets array
        dp = [-1] * n
        subsets = [set() for _ in range(n)]

        # Initially each number forms a singleton subset
        for i in range(n):
            subsets[i].add(nums[i])

        largestSubsetIdx = 0  # Index of largest subset found

        # Calculate largest subset for each number
        for i in range(n):
            if self.calc(nums, dp, subsets, i) > dp[largestSubsetIdx]:
                largestSubsetIdx = i

        # Return the largest subset found
        return list(subsets[largestSubsetIdx])

Complexity

  • Time complexity: $O(n^2 \log n)$

    1. Sorting the Array: The first step in largestDivisibleSubset is sorting the nums array, which takes $O(n \log n)$ time.

    2. Calculation of DP values: We then iterate through each element to calculate the largest subset ending at each index. For each index i, the calc function iterates over every previous index j to find the largest subset that can end at i. This nested iteration results in time complexity $O(n^2)$ for the dynamic programming computation.

    3. Recursive calc Calls: Within each call to calc, there are calls to calc for previous indices. However, since each calc(nums, dp, subsets, i) call result is stored once computed, this effectively means at most one calc is computed per index i. Memoization ensures this does not affect the overall asymptotic complexity beyond the nested loop iteration.

    4. Constructing the Subsets: Constructing the subsets or combining them ends up being linear with respect to the number of operations performed due to the set operations. The complexity of inserting elements from one set into another is dominated by the sorting and iteration operations, leading it to be effectively amortized over its operations. This contributes at most an additional factor of $O(\log n)$ per op due to set properties due to combining subsets, considering each element at most once when constructing the final subset.

    Thus, the predominant operations, including sorting and evaluating combinations, drive the time complexity to $O(n^2 \log n)$.

  • Space complexity: $O(n^2)$

    1. DP Array: We use an array dp of size n to store the largest subset size ending at each index, which contributes $O(n)$ to space complexity.

    2. Subsets Storage: subsets, an array of sets, is used to store individual subsets. In the worst case, each subset may contain all n elements, contributing $O(n^2)$ space.

    3. Call Stack Utilization: Due to the recursive nature of calc, additional stack space proportional to the recursion depth is used. However, the recursion depth only extends as far back as each previous element, effectively $O(n)$ in depth due to memoization and each number being checked exactly once.

    Overall, the space complexity is thus dominated by the storage requirements for subsets, which results in $O(n^2)$ space complexity.

Disclaimer: All reference materials on this website are sourced from the internet and are intended for learning purposes only. If you believe any content infringes upon your rights, please contact me at csnote.cc@gmail.com, and I will remove the relevant content promptly.


Feedback Welcome: If you notice any errors or areas for improvement in the articles, I warmly welcome your feedback and corrections. Your input will help this blog provide better learning resources. This is an ongoing process of learning and improvement, and your suggestions are valuable to me. You can reach me at csnote.cc@gmail.com.