LeetCode Solutions Blog

Largest Divisible Subset

Number: 368

Difficulty: Medium

Paid? No

Problem Description

Given a set of distinct positive integers, the task is to return the largest subset such that every pair (a, b) in the subset meets the condition: either a % b == 0 or b % a == 0. If multiple solutions exist, any valid answer can be returned.

Key Insights

Sorting the array helps because if a is a divisor of b, then a is less than or equal to b.
Use dynamic programming to build the largest divisible subset ending at each number.
Keep track of the previous index for each element to later reconstruct the subset.
The problem is analogous to finding the longest chain where the divisibility condition is maintained.

Space and Time Complexity

Time Complexity: O(n^2) due to the double loop over the sorted array. Space Complexity: O(n) for storing the dp and predecessor arrays.

Solution

The approach is to first sort the input array, then use dynamic programming (DP) to build an array where each entry contains the length of the largest subset ending at that index. For every number, iterate through its previous numbers, and if the previous number divides the current number, update the DP value and record the predecessor. Finally, backtrack from the index with the maximum DP value to reconstruct the largest divisible subset.

Code Solutions

# Python solution for Largest Divisible Subset

def largestDivisibleSubset(nums):
    # Edge case: if the list is empty, return an empty list.
    if not nums:
        return []
    
    # Sort the array to ensure divisibility condition holds with increasing order.
    nums.sort()
    n = len(nums)
    
    # dp[i] will store the size of the largest divisible subset ending with nums[i].
    dp = [1] * n
    # prev[i] stores the previous index for nums[i] in the largest subset.
    prev = [-1] * n
    
    # Variables to track the index and size of the largest subset found.
    maxSubsetSize = 0
    maxSubsetIndex = 0
    
    # Build the dp array with nested loop.
    for i in range(n):
        for j in range(i):
            # Check divisibility condition.
            if nums[i] % nums[j] == 0:
                # If including nums[i] extends the subset ending at nums[j].
                if dp[j] + 1 > dp[i]:
                    dp[i] = dp[j] + 1
                    prev[i] = j
        # Update maximum subset size and index.
        if dp[i] > maxSubsetSize:
            maxSubsetSize = dp[i]
            maxSubsetIndex = i
    
    # Reconstruct the largest divisible subset.
    result = []
    while maxSubsetIndex != -1:
        result.append(nums[maxSubsetIndex])
        maxSubsetIndex = prev[maxSubsetIndex]
    
    # Reverse the result as we reconstructed it backward.
    return result[::-1]

# Example usage:
print(largestDivisibleSubset([1,2,4,8]))