algoadvance

Leetcode 368. Largest Divisible Subset

Problem Statement

Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies:

Si % Sj == 0 or Sj % Si == 0

If there are multiple solutions, return any of them.

Clarifying Questions

  1. Are all elements in the input array distinct?
    • Yes, confirmed by the problem statement.
  2. Can the input array be empty? What should be the output in that case?
    • Yes, if the input array is empty, the output should be an empty subset.
  3. Are there any constraints on the size of the input array?
    • No specific constraints are given, but typical constraints for LeetCode problems usually apply.

Strategy

Step-by-Step Plan

  1. Sort the array: Begin by sorting the array. This allows us to more easily check the divisibility conditions progressively.
  2. Dynamic Programming Array Setup: Use a DP array where dp[i] represents the size of the largest divisible subset ending with nums[i].
  3. Previous Index Tracker: Use an array to track the previous index in the largest subset for reconstruction purposes.
  4. DP array Update: Update the DP array by iterating over each element and checking all previous elements for divisibility.
  5. Reconstruct the Largest Subset: Use the DP values and previous index tracker to reconstruct the largest subset from the DP table.
#include <vector>
#include <algorithm>

std::vector<int> largestDivisibleSubset(std::vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return {};
    
    std::sort(nums.begin(), nums.end());
    std::vector<int> dp(n, 1);
    std::vector<int> prev(n, -1);

    int maxSubsetSize = 1;
    int maxSubsetIndex = 0;

    // Fill dp and prev arrays
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (nums[i] % nums[j] == 0 && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
                prev[i] = j;
            }
        }
        if (dp[i] > maxSubsetSize) {
            maxSubsetSize = dp[i];
            maxSubsetIndex = i;
        }
    }

    // Reconstruct the largest subset
    std::vector<int> largestSubset;
    for (int i = maxSubsetIndex; i >= 0; i = prev[i]) {
        largestSubset.push_back(nums[i]);
        if (prev[i] == i) break;
    }

    std::reverse(largestSubset.begin(), largestSubset.end());
    return largestSubset;
}

Time Complexity

Overall Time Complexity

The combined time complexity is (O(n^2)), which is dominated by the dynamic programming update steps.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI