Leetcode 368. Largest Divisible Subset

Problem Explanation and Example

The problem requests to find the largest subset from a given set of distinct positive integers where every pair satisfies a divisibility condition. Every pair (Si, Sj) of elements in the subset should satisfy the condition: Si % Sj = 0 or Sj % Si = 0.

For example, given the set [1,2,3], the largest subset that satisfies the conditions is [1,2] or [1,3].

Solution Approach

The approach used here is dynamic programming and sorting.

First, we sort the array to ensure that every possible subset of array nums that ends at nums[i] (for all i) will be made up of numbers in nums[0] through nums[i] only.

Next, we use the dynamic programming (DP). We create two arrays:

• sizeEndsAt[], which stores the largest size of the subset that ends at each index. We initialize this array to 1 because every number is by itself a subset.
• prevIndex[], which stores the index of the previous number in the large subset that ends with number at current index.

We set a two pointers (i and j) and move them to find the maximum size of subset that ends at nums[i].

Lastly, once we get maximum size, we can get all elements in it by iterating the nums[] and prevIndex[] array from the largest subset index.

Python Solution

Here is how we can implement the solution in Python.

1
2python
3class Solution:
4    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
5        # length of list
6        n = len(nums)
7        
8        # sort the array
9        nums.sort()
10        
11        # Store maximum size and index
12        maxSize, maxIndex = -1, -1
13
14        # dp[i] is going to store size of largest divisible subset beginning with arr[i]
15        dp = [0]*n
16        
17        # prev[i] is going to store index of previous element in largest divisible subset beginning with arr[i]
18        prev = [-1]*n
19        
20        # Fill values for first two indexes
21        dp[0] = 1
22        
23        # Iterate and fill values in dp[]
24        for i in range(1, n):
25            for j in range(i-1, -1, -1):
26                # If nums[i] is divisible by nums[j]
27                if nums[i]%nums[j] == 0:
28                    if dp[i] < dp[j] + 1:
29                        dp[i] = dp[j]+1
30                        prev[i] = j
31                         
32            # update maximum subset size, and its index
33            if dp[i] > maxSize:
34                maxSize = dp[i]
35                maxIndex = i
36        
37        # get elements using maxIndex in dp[]
38        result = []
39        while maxIndex != -1:
40            result.append(nums[maxIndex])
41            maxIndex = prev[maxIndex]
42        
43        return result

In this python solution, we use dynamic programming along with two arrays dp and prev to keep track of the elements in largest divisible subset. We also update the maximum subset size and its index simultaneously. We iterate from the highest index to find all elements in the largest divisible subset.

We return this subset as the result. Although this solution requires sorting and therefore will take at least O(N log N) where N is the size of the input. However, the time complexity of the overall solution is O(N^2), due to the nested loop, making it reasonable for arrays up to a few thousands in size.

After the solution, you can test it with different test cases to ensure it works as expected.## JavaScript Solution Here is how we can implement the solution in JavaScript.

1
2javascript
3var largestDivisibleSubset = function(nums) {
4    if (nums.length == 0)
5        return nums
6        
7    nums.sort((a, b) => a - b)
8
9    let n = nums.length
10    
11    let dp = new Array(n)
12    dp.fill(1)
13    
14    let prev = new Array(n)
15    prev.fill(-1)
16    
17    let maxSize = 1
18    let maxIndex = 0
19    
20    for (let i = 1; i < n; i++) {
21        for (let j = i - 1; j >= 0; j--) {
22            if (nums[i] % nums[j] == 0 && 1 + dp[j] > dp[i]) {
23                dp[i] = 1 + dp[j]
24                prev[i] = j
25            }
26        }
27        if (dp[i] > maxSize) {
28            maxSize = dp[i]
29            maxIndex = i
30        }
31    }
32    
33    let result = []
34    while (maxIndex != -1) {
35        result.push(nums[maxIndex])
36        maxIndex = prev[maxIndex]
37    }
38    
39    return result
40}

This JavaScript code proceeds similarly to the Python one. We start by initializing two arrays of the same length as nums, dp and prev to 1 and -1 respectively. We then loop through nums, checking the divisibility condition and updating dp and prev accordingly. Meanwhile, we track the largest subset size and its index. At last, result is filled with the elements of the largest divisible subset and is returned.

The time and space complexities are still O(N^2) and O(N), respectively. This is again because we use dynamic programming with a 2D array, which requires us to both store and loop through N elements.

Java Solution

Here is how we can implement the solution in Java.

1
2java
3import java.util.Arrays;
4import java.util.LinkedList;
5import java.util.List;
6
7class Solution {
8    public List<Integer> largestDivisibleSubset(int[] nums) {
9        int n = nums.length;
10        int[] dp = new int[n];
11        int[] prev = new int[n];
12        Arrays.fill(dp, 1);
13        Arrays.fill(prev, -1);
14  
15        Arrays.sort(nums);
16  
17        int maxSize = 0, maxIndex = -1;
18        for(int i = 0; i < n; i++) {
19            for(int j = i - 1; j >= 0; j--) {
20                if(nums[i] % nums[j] == 0 && dp[i] < dp[j] + 1) {
21                    dp[i] = dp[j] + 1;
22                    prev[i] = j;
23                }
24            }
25            if(dp[i] > maxSize) {
26                maxSize = dp[i];
27                maxIndex = i;
28            }
29        }
30    
31        List<Integer> result = new LinkedList<>();
32        while(maxIndex != -1) {
33            result.add(0, nums[maxIndex]);
34            maxIndex = prev[maxIndex];
35        }
36      
37        return result;
38    }
39}

In this Java solution, the code structure and the logic behind it remain the same as in our previous solutions. Here, we make use of Java’s built-in Arrays and LinkedList classes for creating and handling arrays and lists. The time complexity of this solution is also O(N^2) due to the nested loop, while the space complexity is O(N) due to the storage requirements of dp and prev arrays.

It's recommended to test your solutions against various test cases to ensure correctness. Make sure to include edge cases, such as when nums is empty or contains only one or two elements.