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 soluti

largestDivisibleSubset.js

/**
 * Finds the largest subset of numbers from `nums` such that every pair (i, j) 
 * in the subset satisfies:
 * nums[i] % nums[j] === 0 or nums[j] % nums[i] === 0.
 *
 * @param {number[]} nums - Array of distinct positive integers.
 * @return {number[]} - The largest divisible subset.
 */
var largestDivisibleSubset = function(nums) {
    // Edge case: If the input is empty, return an empty subset.
    if (nums.length === 0) return [];

    // Step 1: Sort the numbers in ascending order.
    // Sorting simplifies finding divisible pairs since smaller numbers
    // divide larger ones more easily.
    nums.sort((a, b) => a - b);

    // Step 2: Initialize dynamic programming (dp) array and predecessor array.
    const dp = new Array(nums.length).fill(1); // dp[i]: Maximum size of subset ending with nums[i].
    const prev = new Array(nums.length).fill(-1); // prev[i]: Index of the previous element in the subset.

    let maxSize = 1; // Tracks the size of the largest divisible subset.
    let maxIndex = 0; // Tracks the ending index of the largest divisible subset.

    // Step 3: Fill the dp and prev arrays.
    for (let i = 1; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            // Check divisibility condition and update dp[i] if a larger subset is found.
            if (nums[i] % nums[j] === 0 && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1; // Update size of subset ending at nums[i].
                prev[i] = j;       // Update predecessor to nums[j].
            }
        }

        // Update maxSize and maxIndex if dp[i] becomes the new maximum.
        if (dp[i] > maxSize) {
            maxSize = dp[i];
            maxIndex = i;
        }
    }

    // Step 4: Reconstruct the largest divisible subset.
    const result = [];
    while (maxIndex !== -1) {
        result.push(nums[maxIndex]); // Add current element to the result.
        maxIndex = prev[maxIndex];  // Move to the predecessor element.
    }

    // Step 5: Reverse the result to restore original order.
    return result.reverse();
};