368. Largest Divisible Subset

Problem Description

Given a non-empty set of nums containing distinct positive integers, the task is to find the largest subset of these integers such that each pair of numbers in the subset, (answer[i], answer[j]), is in a relationship where one of the numbers is a multiple of the other. This means for any two numbers in the subset, either one will be divisible by the other without leaving a remainder. The subset containing the highest number of such numbers needs to be identified. If more than one subset fits this requirement, any of them may be returned as the solution.

Intuition

To solve this problem, we need an efficient way to determine relationships between numbers in terms of divisibility, and we want to build the largest group (subset) of numbers where each pair of numbers meets the divisibility condition.

The first insight is that if we sort the list of numbers nums in ascending order, any larger number can only be divisible by a smaller number and not vice versa. This imposes an order on potential divisibility relationships.

The second insight is that we can use Dynamic Programming to build up knowledge of the largest divisible subset up to any given index as we iterate through our sorted list. We define an array f[i] to represent the size of the largest divisible subset that includes nums[i] as the largest number in the subset. So for each number nums[i], we look back at all previous numbers nums[j] where j < i and update f[i] if nums[i] % nums[j] == 0.

Lastly, knowing the size of the largest subset isn't enough; we want the subset itself. We keep track of the index k at which we attain the maximum size of the subset. Once we finish populating our f array, we can backtrack from nums[k] and construct the actual subset by looking at elements that could be used to reach nums[k]. To construct the result, we traverse in reverse, starting from nums[k] going backward, and add numbers to our subset ans that have the correct divisibility property and help us reach the previously calculated optimum size m at each step until we've constructed the full largest subset.

Learn more about Math, Dynamic Programming and Sorting patterns.

Solution Approach

The solution implements Dynamic Programming, which is a method to solve problems by combining the solutions of subproblems.

Let's walk through the code and explain the solution's approach:

1. First, the list nums is sorted so we can guarantee that for any pair (nums[i], nums[j]) where i > j, nums[i] can only be divisible by nums[j] and not vice versa.

1nums.sort()

2. The variable n is initialized to the length of nums, and an array f of the same length is created with all elements set to 1. This array will hold the size of the largest divisible subset ending with nums[i].

1n = len(nums)
2f = [1] * n

3. Two variables, k and m, are used. k is the index at which the largest subset ends, and m will hold the size of the largest subset.

1k = 0

4. We iterate through each element nums[i] from start to end, and for each i, we iterate backwards from i - 1 to 0 to check all possible nums[j] that nums[i] could be divisible by. If nums[i] % nums[j] is 0, meaning nums[j] divides nums[i] without a remainder, we update f[i] if it would lead to a larger subset size than currently recorded at f[i].

1for i in range(n):
2    for j in range(i):
3        if nums[i] % nums[j] == 0:
4            f[i] = max(f[i], f[j] + 1)

5. While updating f[i], we also keep track of the maximum subset size we've seen so far and the corresponding index k.

1if f[k] < f[i]:
2    k = i

6. Now the variable m is assigned to the length of the largest subset.

1m = f[k]

7. To re-construct the actual subset, we initialize an empty list ans and loop backwards from the index k of the largest number belonging to the largest divisible subset. We decrement m each time we add a new element to ans. For each element we consider, it must satisfy two conditions: nums[k] % nums[i] == 0 (divisibility) and f[i] == m (it contributes to the maximum subset size).

1i = k
2ans = []
3while m:
4    if nums[k] % nums[i] == 0 and f[i] == m:
5        ans.append(nums[i])
6        k, m = i, m - 1
7    i -= 1

8. Finally, ans is returned, which contains the elements of nums forming the largest divisible subset.

1return ans

The use of sorting, coupled with dynamic programming and some clever backtracking, enables this solution to find the largest subset efficiently. The Dynamic Programming pattern here helps avoid redundant re-computation by storing optimal sub-solutions in the array f.

Example Walkthrough

Let's illustrate the solution approach with an example. Consider the following small set of distinct positive integers: nums = [1, 2, 4, 8].

1. Sort the array nums. In this example, nums is already sorted in ascending order: [1, 2, 4, 8].

2. Initialize n = len(nums) which is 4 in our case, and f = [1, 1, 1, 1], corresponding to the fact that the largest divisible subset including each number individually is just the number itself.

3. Initialize k = 0 to keep track of the index of the largest subset, although its value will likely change as we iterate through the array.

4. Iterate through each element nums[i]. We check all previous elements nums[j] to find if nums[i] can be made larger by including nums[j]. As 1 divides every other integer, f will become [1, 2, 3, 4] by the end.

5. During iteration, we keep track of the maximum subset size and the index k. After completion, k = 3 (corresponding to number 8) and the maximum subset size m = f[k] = 4.

6. To reconstruct the subset, we start with ans = [] and loop backwards from k = 3. As we check nums[i] we look for divisibility (nums[k] % nums[i] == 0) and if f[i] equals m. We find that all elements in nums satisfy this, so sequentially, ans becomes [8], [8, 4], [8, 4, 2], and finally [8, 4, 2, 1].

7. The resulting subset, which is the largest one where every pair of elements are divisible by one another, is [8, 4, 2, 1].

By following these steps, the solution capitalizes on the sorted property of the array and the previously computed subset sizes, effectively avoiding redundant calculations and leading to a more efficient algorithm.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the code is determined by the nested loops and the operations within them.

• The outer loop runs n times where n is the number of elements in nums.
• The inner loop, for each element of the outer loop, runs a maximum of i times which is less than n.
• Therefore, in total, it has a complexity of approximately O(n^2) due to the double-loop structure.

The while loop at the end of the code runs a maximum of n times corresponding to the size of the nums list. The operations inside are of constant time. However, this does not affect the overall time complexity since it's linear and the dominant factor is the O(n^2) from the nested loops. Hence the overall time complexity remains O(n^2).

Space Complexity

The space complexity of the code is determined by the additional storage used:

• The f list which is of size n contributes O(n) to the space complexity.
• The ans list could potentially reach the same size as nums in the case that all elements are multiples of each other. Thus, it also contributes O(n) to the space complexity.

The variables k, i, and m use constant space.

Therefore, the overall space complexity is O(n) as it relies on the storage required for the f and ans lists, which scale linearly with the size of the input nums.

Learn more about how to find time and space complexity quickly using problem constraints.