D
DevExCode

LeetCode 368: Largest Divisible Subset Solution

Master LeetCode problem 368 (Largest Divisible Subset), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

368. Largest Divisible Subset

Medium
ArrayMathDynamic ProgrammingSorting

Problem Explanation

Explanation

To solve this problem, we can sort the input array nums. Then, we can utilize dynamic programming to keep track of the longest divisible subset ending at each element. We iterate through the sorted array and for each element, we find the previous element that divides the current element. By keeping track of the maximum length subset ending at each element, we can find the overall largest divisible subset.

Algorithm:

  1. Sort the nums array in ascending order.
  2. Initialize two arrays dp and prev of size equal to the length of nums.
  3. Initialize variables maxLen, maxIndex.
  4. Iterate over each element nums[i] in the sorted array.
    • For each element, iterate from index 0 to i-1 to find the previous element that divides nums[i].
    • Update dp[i] and prev[i] accordingly.
    • Keep track of the maximum length subset and its ending index.
  5. Reconstruct the subset using the prev array starting from maxIndex and going backwards.
  6. Return the subset.

Time Complexity:

The time complexity of this algorithm is O(n^2) where n is the number of elements in the input array nums.

Space Complexity:

The space complexity of this algorithm is O(n) where n is the number of elements in the input array nums.

Solution Code

class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int[] dp = new int[n];
        int[] prev = new int[n];
        int maxLen = 0, maxIndex = 0;
        
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            prev[i] = -1;
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    prev[i] = j;
                }
            }
            if (dp[i] > maxLen) {
                maxLen = dp[i];
                maxIndex = i;
            }
        }
        
        List<Integer> result = new ArrayList<>();
        while (maxIndex != -1) {
            result.add(nums[maxIndex]);
            maxIndex = prev[maxIndex];
        }
        
        return result;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 368 (Largest Divisible Subset)?

This page provides optimized solutions for LeetCode problem 368 (Largest Divisible Subset) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 368 (Largest Divisible Subset)?

The time complexity for LeetCode 368 (Largest Divisible Subset) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 368 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 368 in Java, C++, or Python.

Back to LeetCode Solutions