368. Largest Divisible Subset – Leetcode Solutions

Example 1:

Input: nums = [1,2,3]
Output: [1,2]
Explanation: [1,3] is also accepted.

Example 2:

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

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        # Edge case: if the input list is empty, return an empty list
        if not nums:
            return []
        
        # Step 1: Sort the input list
        nums.sort()
        n = len(nums)
        
        # Step 2: Initialize the dp array and parent tracking array
        dp = [1] * n  # dp[i] will store the size of the largest subset ending with nums[i]
        parent = [-1] * n  # parent[i] will store the index of the previous element in the subset
        
        # Variable to track the index of the last element in the largest subset
        max_size = 0
        max_index = -1
        
        # Step 3: Populate the dp and parent arrays
        for i in range(n):
            for j in range(i):
                # If nums[i] is divisible by nums[j], try to extend the subset
                if nums[i] % nums[j] == 0 and dp[i] < dp[j] + 1:
                    dp[i] = dp[j] + 1
                    parent[i] = j  # Track the previous element in the chain
            
            # Update the maximum subset size and its ending index
            if dp[i] > max_size:
                max_size = dp[i]
                max_index = i
        
        # Step 4: Reconstruct the largest divisible subset
        result = []
        current_index = max_index
        while current_index != -1:
            result.append(nums[current_index])
            current_index = parent[current_index]
        
        # Since we reconstructed the result from the end, reverse it to get the correct order
        result.reverse()
        return result

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        // Step 1: Sort the input array in ascending order.
        // Sorting helps in simplifying the divisibility checks because 
        // for any two numbers a and b, if a divides b and a < b, 
        // we only need to check the previous smaller numbers.
        sort(nums.begin(), nums.end());
        
        int n = nums.size();  // Get the size of the input array
        vector<int> dp(n, 1);  // dp[i] will store the size of the largest divisible subset ending at index i
        vector<int> prev(n, -1);  // prev[i] will store the index of the previous element in the subset for backtracking
        
        int maxIndex = 0;  // This will store the index of the last element in the largest divisible subset
        
        // Step 2: Build the dp array and prev array.
        // We will use dynamic programming to calculate the largest divisible subset ending at each index.
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                // If nums[i] is divisible by nums[j], we can extend the divisible subset ending at j
                if (nums[i] % nums[j] == 0) {
                    // If extending the subset results in a larger subset, update dp[i] and prev[i]
                    if (dp[i] < dp[j] + 1) {
                        dp[i] = dp[j] + 1;
                        prev[i] = j;  // Record the index of the previous element
                    }
                }
            }
            // Update maxIndex to the index with the largest subset so far
            if (dp[i] > dp[maxIndex]) {
                maxIndex = i;
            }
        }
        
        // Step 3: Backtrack from maxIndex to find the elements in the largest divisible subset
        vector<int> result;
        int current = maxIndex;
        while (current != -1) {
            result.push_back(nums[current]);
            current = prev[current];  // Move to the previous element in the subset
        }
        
        // Step 4: The result array will contain the largest divisible subset in reverse order.
        // Reverse it to get the correct order.
        reverse(result.begin(), result.end());
        
        return result;  // Return the largest divisible subset
    }
};

var largestDivisibleSubset = function(nums) {
    // Step 1: Edge case - if the input array is empty, return an empty array.
    if (nums.length === 0) return [];

    // Step 2: Sort the numbers in ascending order.
    // This helps in making sure that when we check divisibility, we only need to check previous elements.
    nums.sort((a, b) => a - b);

    // Step 3: Create an array `dp` where dp[i] represents the length of the largest divisible subset
    // that ends with nums[i]. Initialize each value to 1 since each element by itself is a valid subset.
    let dp = Array(nums.length).fill(1);

    // Step 4: Create an array `previous` to trace the indices of the elements in the largest divisible subset.
    // Initialize it with -1 indicating that there's no previous element initially.
    let previous = Array(nums.length).fill(-1);

    // Step 5: Variables to keep track of the index of the maximum length subset.
    let maxIndex = 0;

    // Step 6: Use a nested loop to populate `dp` and `previous` arrays.
    // The outer loop picks each number as the last element of the subset.
    // The inner loop finds the largest divisible subset that can end with nums[i].
    for (let i = 1; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            // Check if nums[i] is divisible by nums[j].
            if (nums[i] % nums[j] === 0) {
                // If adding nums[i] to the subset ending with nums[j] results in a larger subset,
                // update dp[i] and track the previous element.
                if (dp[i] < dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                    previous[i] = j;
                }
            }
        }

        // Keep track of the index of the largest subset found.
        if (dp[i] > dp[maxIndex]) {
            maxIndex = i;
        }
    }

    // Step 7: Reconstruct the largest divisible subset using the `previous` array.
    let result = [];
    let currentIndex = maxIndex;
    while (currentIndex !== -1) {
        result.push(nums[currentIndex]);
        currentIndex = previous[currentIndex];
    }

    // Step 8: Since we traversed from the end to the beginning, reverse the result to get the correct order.
    return result.reverse();
};

class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        // If the input array is empty, return an empty list
        if (nums == null || nums.length == 0) {
            return new ArrayList<>();
        }

        // Step 1: Sort the array to make sure that for any valid pair (a, b) in the subset,
        // we can ensure that a <= b, and a divides b.
        Arrays.sort(nums);

        int n = nums.length; // Get the length of the input array

        // Step 2: Create a dp array where dp[i] will store the size of the largest divisible subset
        // ending with the element nums[i].
        int[] dp = new int[n];

        // Initialize all dp values to 1 since the smallest subset possible for any number is just the number itself.
        Arrays.fill(dp, 1);

        // This array will help track the previous index in the subset chain.
        int[] previousIndex = new int[n];

        // Fill previousIndex with -1 to indicate no previous index for now.
        Arrays.fill(previousIndex, -1);

        // Variable to track the index of the last element in the largest subset.
        int maxIndex = 0;

        // Step 3: Fill the dp array based on the divisible property.
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                // If nums[i] is divisible by nums[j], and including nums[i] results in a larger subset,
                // then update dp[i] and track the previous index.
                if (nums[i] % nums[j] == 0 && dp[i] < dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                    previousIndex[i] = j; // Track the previous element index
                }
            }

            // Update maxIndex if we found a larger subset ending at index i
            if (dp[i] > dp[maxIndex]) {
                maxIndex = i;
            }
        }

        // Step 4: Reconstruct the largest divisible subset using the previousIndex array.
        List<Integer> result = new ArrayList<>();
        int currentIndex = maxIndex;

        // Backtrack from maxIndex to collect all elements of the largest divisible subset
        while (currentIndex != -1) {
            result.add(nums[currentIndex]);
            currentIndex = previousIndex[currentIndex];
        }

        // Since we backtracked, the elements are in reverse order, so reverse the result list.
        Collections.reverse(result);

        // Return the largest divisible subset
        return result;
    }
}