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:

If there are multiple solutions, return any subset.

Clarifying Questions

  1. Input Format:
    • What is the input format?
      • The input will be an array of distinct positive integers.
  2. Output Format:
    • What should be the output format?
      • The output should be a list (array) of integers representing the largest divisible subset.
  3. Constraints:
    • What is the range of the array size n?
      • 1 ≤ n ≤ 1000.
    • Are all elements in the input array distinct positive integers?
      • Yes, all elements are distinct positive integers.

  4. Examples:

    • Example 1:
      • Input: [1, 2, 3]
      • Output: [1, 2] or [1, 3]
    • Example 2:
      • Input: [1, 2, 4, 8]
      • Output: [1, 2, 4, 8]

Strategy

  1. Sorting:
    • First, sort the array. Sorting helps because if we have say 2 and 4, and since 4 % 2 == 0, any number which is divisible by 4 will also be divisible by 2.
  2. Dynamic Programming (DP):
    • Use a DP array dp where dp[i] represents the length of the largest divisible subset ending with nums[i].
    • Use another array prev to keep track of the previous element index in the subset.
  3. Reconstruction of the subset:
    • Once the DP array is filled, reconstruct the subset using the prev array.
  4. Pseudocode:
    • Sort the input array.
    • Initialize DP and previous index arrays.
    • Iterate over each pair of elements (nested loops), update DP and previous index arrays.
    • Find the maximum value in the DP array to get the length of the largest subset and its last index.
    • Reconstruct the largest subset by backtracking using the prev array.

Code

import java.util.*;

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

        Arrays.sort(nums);
        int n = nums.length;
        int[] dp = new int[n];
        int[] prev = new int[n];

        // Initialize dp array: each element is a subset of length 1
        Arrays.fill(dp, 1);
        Arrays.fill(prev, -1);

        int maxIndex = 0;

        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] > dp[maxIndex]) {
                maxIndex = i;
            }
        }

        List<Integer> result = new ArrayList<>();
        for (int i = maxIndex; i >= 0; i = prev[i]) {
            result.add(nums[i]);
            if (prev[i] == i) {
                break;
            }
        }

        Collections.reverse(result);
        return result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums1 = {1, 2, 3};
        System.out.println(sol.largestDivisibleSubset(nums1)); // Output: [1, 2] or [1, 3]

        int[] nums2 = {1, 2, 4, 8};
        System.out.println(sol.largestDivisibleSubset(nums2)); // Output: [1, 2, 4, 8]
    }
}

Time Complexity

The implementation is efficient for the given constraints and follows a dynamic programming approach to solve the problem optimally.

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