Largest Divisible Subset - LeetCode Daily Challenge

Feb 9, 2024 — Aakash Verma

Problem Statement

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: 2 % 1 gives 0. [1,3] is also accepted as 3 % 1 gives 0.

Example 2

Input: nums = [1,2,4,8]
Output: [1,2,4,8]

Try here before watching the video.

Video Solution

Recursive DP (Bottom-Up Fashion)

Java Code

class Solution {

    private Map<Integer, List<Integer>> endingSubset;

    private List<Integer> findSubsetEndingAtNum(int i, int[] nums) {
        if(endingSubset.containsKey(i)) {
            return endingSubset.get(i);
        }

        List<Integer> localMaxSubset = new ArrayList<>();
        for(int k = 0; k < i; k++) {
            if(nums[i] % nums[k] == 0) {
                List<Integer> subset = findSubsetEndingAtNum(k, nums);
                if(localMaxSubset.size() < subset.size()) {
                    localMaxSubset = subset;
                }
            }
        }

        List<Integer> newSubset = new ArrayList<>();
        newSubset.addAll(localMaxSubset);
        newSubset.add(nums[i]);

        endingSubset.put(i, newSubset);
        return newSubset;
    }   

    public List<Integer> largestDivisibleSubset(int[] nums) {
        int n = nums.length;
        if(n == 0) {
            return new ArrayList<>();
        }

        this.endingSubset = new HashMap<>();
        Arrays.sort(nums);

        List<Integer> maxSubset = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            List<Integer> subset = findSubsetEndingAtNum(i, nums);
            if(maxSubset.size() < subset.size()) {
                maxSubset = subset;
            }
        }

        return maxSubset;
    }
}

C++ Code

class Solution {
private:
    unordered_map<int, vector<int>> endingSubset;

    vector<int> findSubsetEndingAtNum(int i, vector<int>& nums) {
        if (endingSubset.count(i)) {
            return endingSubset[i];
        }

        vector<int> localMaxSubset;
        for (int k = 0; k < i; k++) {
            if (nums[i] % nums[k] == 0) {
                vector<int> subset = findSubsetEndingAtNum(k, nums);
                if (localMaxSubset.size() < subset.size()) {
                    localMaxSubset = subset;
                }
            }
        }

        vector<int> newSubset = localMaxSubset;
        newSubset.push_back(nums[i]);

        endingSubset[i] = newSubset;
        return newSubset;
    }

public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {
            return vector<int>();
        }

        endingSubset.clear();
        sort(nums.begin(), nums.end());

        vector<int> maxSubset;
        for (int i = 0; i < n; i++) {
            vector<int> subset = findSubsetEndingAtNum(i, nums);
            if (maxSubset.size() < subset.size()) {
                maxSubset = subset;
            }
        }

        return maxSubset;
    }
};

Python Code

class Solution:
    def __init__(self):
        self.endingSubset = {}

    def findSubsetEndingAtNum(self, i, nums):
        if i in self.endingSubset:
            return self.endingSubset[i]

        localMaxSubset = []
        for k in range(i):
            if nums[i] % nums[k] == 0:
                subset = self.findSubsetEndingAtNum(k, nums)
                if len(localMaxSubset) < len(subset):
                    localMaxSubset = subset

        newSubset = localMaxSubset + [nums[i]]
        self.endingSubset[i] = newSubset
        return newSubset

    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        if not nums:
            return []

        nums.sort()
        maxSubset = []
        for i in range(len(nums)):
            subset = self.findSubsetEndingAtNum(i, nums)
            if len(maxSubset) < len(subset):
                maxSubset = subset

        return maxSubset

Javascript Code

var largestDivisibleSubset = function(nums) {
    const endingSubset = new Map();

    const findSubsetEndingAtNum = (i, nums) => {
        if (endingSubset.has(i)) {
            return endingSubset.get(i);
        }

        let localMaxSubset = [];
        for (let k = 0; k < i; k++) {
            if (nums[i] % nums[k] === 0) {
                const subset = findSubsetEndingAtNum(k, nums);
                if (localMaxSubset.length < subset.length) {
                    localMaxSubset = subset;
                }
            }
        }

        const newSubset = localMaxSubset.concat(nums[i]);
        endingSubset.set(i, newSubset);
        return newSubset;
    };

    if (!nums.length) {
        return [];
    }

    nums.sort((a, b) => a - b);

    let maxSubset = [];
    for (let i = 0; i < nums.length; i++) {
        const subset = findSubsetEndingAtNum(i, nums);
        if (maxSubset.length < subset.length) {
            maxSubset = subset;
        }
    }

    return maxSubset;
};

Go Code

func findSubsetEndingAtNum(i int, nums []int, endingSubset map[int][]int) []int {
	if subset, ok := endingSubset[i]; ok {
		return subset
	}

	var localMaxSubset []int
	for k := 0; k < i; k++ {
		if nums[i]%nums[k] == 0 {
			subset := findSubsetEndingAtNum(k, nums, endingSubset)
			if len(localMaxSubset) < len(subset) {
				localMaxSubset = subset
			}
		}
	}

	newSubset := append([]int{}, localMaxSubset...)
	newSubset = append(newSubset, nums[i])
	endingSubset[i] = newSubset
	return newSubset
}

func largestDivisibleSubset(nums []int) []int {
	if len(nums) == 0 {
		return []int{}
	}

	sort.Ints(nums)

	endingSubset := make(map[int][]int)
	maxSubset := []int{}
	for i := 0; i < len(nums); i++ {
		subset := findSubsetEndingAtNum(i, nums, endingSubset)
		if len(subset) > len(maxSubset) {
			maxSubset = subset
		}
	}

	return maxSubset
}

Complexity Analysis

Time complexity: O(N²)
- In the above implementation, we adopt the bottom-up strategy where we first calculate the findSubsetEndingAtNum(Xi) for elements with a lower index. Through the memoization technique, the latter findSubsetEndingAtNum(Xi) calculation could reuse the intermediate ones. As a result, we reach the time complexity O(N²).
Space complexity: O(N²)
- In this implementation, we decide to keep the subset instead of its size, as the intermediate solution. As a result, this would lead to the O(N²) space complexity, with the worst scenario where the entire input list is a divisible set.
- In addition, due to the use of recursion, the program would incur a maximum O(N) space for the call stacks, during the invocation of findSubsetEndingAtNum(Xn) for the last element in the ordered list. Though, overall the space complexity remains as O(N²).

Iterative DP (Bottom-Up Fashion)

Java Code

class Solution {  

    public List<Integer> largestDivisibleSubset(int[] nums) {
        int n = nums.length;
        if(n == 0) {
            return new ArrayList<>();
        }

        Map<Integer, List<Integer>> endingSubset = new HashMap<>();;
        for(int i = 0; i < n; i++) {
            endingSubset.put(i, new ArrayList<>());
        }
        
        Arrays.sort(nums);
        List<Integer> maxSubset = new ArrayList<>();

        for(int i = 0; i < n; i++) {
            List<Integer> localMaxSubset = new ArrayList<>();
            for(int k = 0; k < i; k++) {
                if(nums[i] % nums[k] == 0) {
                    if(localMaxSubset.size() < endingSubset.get(k).size()) {
                        localMaxSubset = endingSubset.get(k);
                    }
                }
            }
            endingSubset.get(i).addAll(localMaxSubset);
            endingSubset.get(i).add(nums[i]);
        }

        for(int i = 0; i < n; i++) {
            if(maxSubset.size() < endingSubset.get(i).size()) {
                maxSubset = endingSubset.get(i);
            }
        }
        
        return maxSubset;
    }
}

C++ Code

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {
            return vector<int>();
        }

        unordered_map<int, vector<int>> endingSubset;
        for (int i = 0; i < n; i++) {
            endingSubset[i] = vector<int>();
        }
        
        sort(nums.begin(), nums.end());
        vector<int> maxSubset;

        for (int i = 0; i < n; i++) {
            vector<int> localMaxSubset;
            for (int k = 0; k < i; k++) {
                if (nums[i] % nums[k] == 0) {
                    if (localMaxSubset.size() < endingSubset[k].size()) {
                        localMaxSubset = endingSubset[k];
                    }
                }
            }
            endingSubset[i].insert(endingSubset[i].end(), localMaxSubset.begin(), localMaxSubset.end());
            endingSubset[i].push_back(nums[i]);
        }

        for (int i = 0; i < n; i++) {
            if (maxSubset.size() < endingSubset[i].size()) {
                maxSubset = endingSubset[i];
            }
        }
        
        return maxSubset;
    }
};

Python Code

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        n = len(nums)
        if n == 0:
            return []

        ending_subset = {i: [] for i in range(n)}
        
        nums.sort()
        max_subset = []

        for i in range(n):
            local_max_subset = []
            for k in range(i):
                if nums[i] % nums[k] == 0:
                    if len(local_max_subset) < len(ending_subset[k]):
                        local_max_subset = ending_subset[k][:]
            ending_subset[i].extend(local_max_subset)
            ending_subset[i].append(nums[i])

        for i in range(n):
            if len(max_subset) < len(ending_subset[i]):
                max_subset = ending_subset[i]
        
        return max_subset

Javascript Code

var largestDivisibleSubset = function(nums) {
    const n = nums.length;
    if (n === 0) {
        return [];
    }

    const endingSubset = {};
    for (let i = 0; i < n; i++) {
        endingSubset[i] = [];
    }
    
    nums.sort((a, b) => a - b);
    let maxSubset = [];

    for (let i = 0; i < n; i++) {
        let localMaxSubset = [];
        for (let k = 0; k < i; k++) {
            if (nums[i] % nums[k] === 0) {
                if (localMaxSubset.length < endingSubset[k].length) {
                    localMaxSubset = endingSubset[k].slice();
                }
            }
        }
        endingSubset[i].push(...localMaxSubset, nums[i]);
    }

    for (let i = 0; i < n; i++) {
        if (maxSubset.length < endingSubset[i].length) {
            maxSubset = endingSubset[i];
        }
    }
    
    return maxSubset;
};

Go Code

func largestDivisibleSubset(nums []int) []int {
	n := len(nums)
	if n == 0 {
		return []int{}
	}

	endingSubset := make(map[int][]int)
	for i := 0; i < n; i++ {
		endingSubset[i] = []int{}
	}
    
	sort.Ints(nums)
	maxSubset := []int{}

	for i := 0; i < n; i++ {
		localMaxSubset := []int{}
		for k := 0; k < i; k++ {
			if nums[i]%nums[k] == 0 {
				if len(localMaxSubset) < len(endingSubset[k]) {
					localMaxSubset = endingSubset[k]
				}
			}
		}
		endingSubset[i] = append(endingSubset[i], localMaxSubset...)
		endingSubset[i] = append(endingSubset[i], nums[i])
	}

	for i := 0; i < n; i++ {
		if len(maxSubset) < len(endingSubset[i]) {
			maxSubset = endingSubset[i]
		}
	}
	
	return maxSubset
}

Complexity Analysis

Time complexity: O(N²)
- In the above implementation, we adopt the iterative bottom-up strategy and we can see the two loops running.
Space complexity: O(N²)
- In this implementation also, we are maintaining endingSubset map which fills subset for every indexed number. Hence, space complexity is still O(N²).

Iterative DP (Space Optimized)

Java Code

class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        int n = nums.length;
        if(n == 0) {
            return new ArrayList<>();
        }

        List<Integer> maxSubset = new ArrayList<Integer>();
        Arrays.sort(nums);
        int parent[] = new int[nums.length];
        int endingSubsetSize[] = new int[nums.length];
        int maxLength = 0, maxSubsetSizeIndex = -1;

        Arrays.fill(endingSubsetSize, 1);
        Arrays.fill(parent, -1);

        for (int i = 0; i < nums.length; i++){
            for (int k = 0; k < i; k++){
                if (nums[i] % nums[k] == 0 && endingSubsetSize[i] < endingSubsetSize[k] + 1){
                    endingSubsetSize[i] = endingSubsetSize[k] + 1;
                    parent[i] = k;
                }
            }
            if (endingSubsetSize[i] > maxLength){
                maxLength = endingSubsetSize[i];
                maxSubsetSizeIndex = i;
            }
        }

        while (maxSubsetSizeIndex != -1){
            maxSubset.add(nums[maxSubsetSizeIndex]);
            maxSubsetSizeIndex = parent[maxSubsetSizeIndex];
        }
        
        return maxSubset;
    }
}

C++ Code

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {
            return vector<int>();
        }

        vector<int> maxSubset;
        sort(nums.begin(), nums.end());
        vector<int> parent(n, -1);
        vector<int> endingSubsetSize(n, 1);
        int maxLength = 0, maxSubsetSizeIndex = -1;

        for (int i = 0; i < n; i++) {
            for (int k = 0; k < i; k++) {
                if (nums[i] % nums[k] == 0 && endingSubsetSize[i] < endingSubsetSize[k] + 1) {
                    endingSubsetSize[i] = endingSubsetSize[k] + 1;
                    parent[i] = k;
                }
            }
            if (endingSubsetSize[i] > maxLength) {
                maxLength = endingSubsetSize[i];
                maxSubsetSizeIndex = i;
            }
        }

        while (maxSubsetSizeIndex != -1) {
            maxSubset.push_back(nums[maxSubsetSizeIndex]);
            maxSubsetSizeIndex = parent[maxSubsetSizeIndex];
        }
        
        reverse(maxSubset.begin(), maxSubset.end());
        return maxSubset;
    }
};

Python Code

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        n = len(nums)
        if n == 0:
            return []

        max_subset = []
        nums.sort()
        parent = [-1] * n
        ending_subset_size = [1] * n
        max_length = 0
        max_subset_size_index = -1

        for i in range(n):
            for k in range(i):
                if nums[i] % nums[k] == 0 and ending_subset_size[i] < ending_subset_size[k] + 1:
                    ending_subset_size[i] = ending_subset_size[k] + 1
                    parent[i] = k
            if ending_subset_size[i] > max_length:
                max_length = ending_subset_size[i]
                max_subset_size_index = i

        while max_subset_size_index != -1:
            max_subset.append(nums[max_subset_size_index])
            max_subset_size_index = parent[max_subset_size_index]

        return max_subset

Javascript Code

var largestDivisibleSubset = function(nums) {
    const n = nums.length;
    if (n === 0) {
        return [];
    }

    const maxSubset = [];
    nums.sort((a, b) => a - b);
    const parent = new Array(n).fill(-1);
    const endingSubsetSize = new Array(n).fill(1);
    let maxLength = 0;
    let maxSubsetSizeIndex = -1;

    for (let i = 0; i < n; i++) {
        for (let k = 0; k < i; k++) {
            if (nums[i] % nums[k] === 0 && endingSubsetSize[i] < endingSubsetSize[k] + 1) {
                endingSubsetSize[i] = endingSubsetSize[k] + 1;
                parent[i] = k;
            }
        }
        if (endingSubsetSize[i] > maxLength) {
            maxLength = endingSubsetSize[i];
            maxSubsetSizeIndex = i;
        }
    }

    while (maxSubsetSizeIndex !== -1) {
        maxSubset.push(nums[maxSubsetSizeIndex]);
        maxSubsetSizeIndex = parent[maxSubsetSizeIndex];
    }
    
    return maxSubset;
};

Go Code

func largestDivisibleSubset(nums []int) []int {
	n := len(nums)
	if n == 0 {
		return []int{}
	}

	maxSubset := []int{}
	sort.Ints(nums)
	parent := make([]int, n)
	endingSubsetSize := make([]int, n)

    for i := 0; i < n; i++ {
        parent[i] = -1
        endingSubsetSize[i] = 1
    }
    
	maxLength := 0
	maxSubsetSizeIndex := -1

	for i := 0; i < n; i++ {
		for k := 0; k < i; k++ {
			if nums[i]%nums[k] == 0 && endingSubsetSize[i] < endingSubsetSize[k]+1 {
				endingSubsetSize[i] = endingSubsetSize[k] + 1
				parent[i] = k
			}
		}
		if endingSubsetSize[i] > maxLength {
			maxLength = endingSubsetSize[i]
			maxSubsetSizeIndex = i
		}
	}

	for maxSubsetSizeIndex != -1 {
		maxSubset = append(maxSubset, nums[maxSubsetSizeIndex])
		maxSubsetSizeIndex = parent[maxSubsetSizeIndex]
	}

	return maxSubset
}

Complexity Analysis

Time Complexity: O(N²), The additional logic to reconstruct the resulting subset would take us an extra O(N) time complexity which is inferior to the main loop that takes O(N²).
Space Complexity: O(N), The vector endingSubsetSize that keeps track of the size of the largest divisible subset which ends with each of the elements, would take O(N) and we are mainting parent array to create subset would take O(N).

Largest Divisible Subset - LeetCode Daily Challenge

Largest Divisible Subset - LeetCode Daily Challenge

Problem Statement

Example 1

Example 2

Video Solution

Recursive DP (Bottom-Up Fashion)

Java Code

C++ Code

Python Code

Javascript Code

Go Code

Complexity Analysis

Iterative DP (Bottom-Up Fashion)

Java Code

C++ Code

Python Code

Javascript Code

Go Code

Complexity Analysis

Iterative DP (Space Optimized)

Java Code

C++ Code

Python Code

Javascript Code

Go Code

Complexity Analysis

On this page