How do you solve Largest Divisible Subset on LeetCode?

Largest Divisible Subset (LeetCode #368) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n²) time complexity and O(n) space complexity. Key insight: Sorting helps in reducing the number of comparisons needed for divisibility.

What is the brute force solution for Largest Divisible Subset?

The brute force approach for Largest Divisible Subset is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves generating all possible subsets of the given array and checking each subset to see if it satisfies the divisibility condition. This method is straightforward but inefficient for larger inputs. The optimal Optimal Solution approach improves this to O(n²).

What algorithm or data structure is used to solve Largest Divisible Subset?

Largest Divisible Subset uses the following concepts: Array, Math, Dynamic Programming, Sorting. The recommended patterns to study are: Dynamic Programming, Sorting.

What are the interview tips for Largest Divisible Subset?

Always consider edge cases, such as when the input array has only one element. Explain your thought process clearly as you work through the problem, especially when transitioning from brute force to optimal solutions. Practice reconstructing the solution from the DP table, as this is often a tricky part.

What are common mistakes when solving Largest Divisible Subset?

Not sorting the array before processing, which can lead to incorrect results. Failing to track the previous indices correctly during the reconstruction of the subset.

#368

Largest Divisible Subset

Medium

ArrayMathDynamic ProgrammingSortingDynamic ProgrammingSorting

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n²)
Space	O(1)	O(n)

💡

Intuition

Time O(n²)Space O(n)

The optimal solution uses dynamic programming to build the largest divisible subset efficiently. By sorting the array first, we can ensure that we only need to check previous elements for divisibility, which reduces unnecessary comparisons.

⚙️

Algorithm

5 steps

1Step 1: Sort the input array.
2Step 2: Initialize a DP array where dp[i] holds the size of the largest divisible subset ending with nums[i].
3Step 3: For each element, check all previous elements to see if they can form a divisible pair, updating dp accordingly.
4Step 4: Track the maximum size and the index of the last element in the largest subset.
5Step 5: Reconstruct the largest subset using the indices stored.

solution.py24 lines

1# Full working Python code
2def largestDivisibleSubset(nums):
3    nums.sort()
4    n = len(nums)
5    dp = [1] * n
6    prev = [-1] * n
7    max_size = 0
8    max_index = -1
9
10    for i in range(n):
11        for j in range(i):
12            if nums[i] % nums[j] == 0:
13                if dp[i] < dp[j] + 1:
14                    dp[i] = dp[j] + 1
15                    prev[i] = j
16        if dp[i] > max_size:
17            max_size = dp[i]
18            max_index = i
19
20    result = []
21    while max_index != -1:
22        result.append(nums[max_index])
23        max_index = prev[max_index]
24    return result[::-1]

ℹ

Complexity note: The time complexity remains O(n²) due to the nested loops for checking divisibility, but we use O(n) space for the dp and prev arrays to store the sizes and previous indices of the subsets.

1Sorting helps in reducing the number of comparisons needed for divisibility.
2Dynamic programming allows us to build solutions incrementally, leveraging previously computed results.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.