368. Largest Divisible Subset

Description

The problem requires finding the largest subset of numbers from a given array such that for any two elements in the subset, one divides the other perfectly. The result should be the largest such subset in terms of size.

Intuition

The main observation here is that the problem relates to divisibility. Sorting the array will help ensure that for any number at index i, the elements before it can be potential divisors, and we can build the subset progressively.

Approach

1. Sorting: First, we sort the array to handle numbers from smallest to largest.
2. Dynamic Programming Approach: We use a cache (or dictionary) to store the largest divisible subset for each number encountered so far.
3. Subset Construction: For each number, we check every number before it and determine if it divides the current number. If it does, and the subset formed by including the current number is larger, we update the subset.
4. Return the Largest Subset: At the end of the iteration, we return the largest subset found, excluding the first element.

Complexity

Time Complexity:

O(n^2), where n is the size of the input array. We iterate over each element and for each element, we check every previous element.

Space Complexity:

O(n), to store the subsets for each number in the cache.

Code

C++

class Solution {
public:
    std::vector largestDivisibleSubset(std::vector& nums) {
        std::sort(nums.begin(), nums.end());
        std::unordered_map> cache;
        std::vector longest;
        
        for (int i = 0; i < nums.size(); i++) {
            int curr = nums[i];
            std::vector arr = {curr};
            
            for (int j = 0; j < i; j++) {
                std::vector prevArray = cache[nums[j]];
                if (curr % prevArray.back() == 0 && prevArray.size() > arr.size()) {
                    arr = prevArray;
                }
            }
            
            arr.push_back(curr);
            if (arr.size() > longest.size()) {
                longest = arr;
            }
            
            cache[curr] = arr;
        }
        
        return std::vector(longest.begin() + 1, longest.end());
    }
};

Python

class Solution:
    def largestDivisibleSubset(self, nums):
        nums.sort()
        cache = {}
        longest = []
        
        for i in range(len(nums)):
            curr = nums[i]
            arr = [curr]
            
            for j in range(i):
                prev_array = cache[nums[j]]
                if curr % prev_array[-1] == 0 and len(prev_array) > len(arr):
                    arr = prev_array[:]
            
            arr.append(curr)
            if len(arr) > len(longest):
                longest = arr
            
            cache[curr] = arr
        
        return longest[1:]

Java

class Solution {
    public List largestDivisibleSubset(int[] nums) {
        Arrays.sort(nums);
        Map> cache = new HashMap<>();
        List longest = new ArrayList<>();
        
        for (int i = 0; i < nums.length; i++) {
            int curr = nums[i];
            List arr = new ArrayList<>(Arrays.asList(curr));
            
            for (int j = 0; j < i; j++) {
                List prevArray = cache.get(nums[j]);
                if (curr % prevArray.get(prevArray.size() - 1) == 0 && prevArray.size() > arr.size()) {
                    arr = new ArrayList<>(prevArray);
                }
            }
            
            arr.add(curr);
            if (arr.size() > longest.size()) {
                longest = arr;
            }
            
            cache.put(curr, arr);
        }
        
        return longest.subList(1, longest.size());
    }
}

JavaScript

var largestDivisibleSubset = function (nums) {
    nums.sort((a, b) => a - b);
    let cache = {};
    let largest = 0;
    let longest = [];
    for (let i = 0; i < nums.length; i++) {
        let curr = nums[i];
        let arr = [curr];
        for (let j = 0; j < i; j++) {
            let prevArray = cache[nums[j]];
            if (curr % prevArray[prevArray.length - 1] === 0 && prevArray.length > arr.length) {
                arr = prevArray//.concat(curr);
            }
        }
        //if(arr[0]!==curr)
        arr = arr.concat(curr);
        if (arr.length > longest.length) {
            longest = arr;
        }
        cache[curr] = arr;
    }
    //console.log(cache)
    return longest.slice(1);
};