Maximum Good Subtree Score - Video Solutions
3575. Maximum Good Subtree Score | Leetcode Biweekly Contest 158
Maximum Good Subtree Score - Video Solution
Watch 4 video solutions for Maximum Good Subtree Score, a hard level problem involving Array, Dynamic Programming, Bit Manipulation. This walkthrough by Amit Dhyani has 570 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given an undirected tree rooted at node 0 with n nodes numbered from 0 to n - 1. Each node i has an integer value vals[i], and its parent is given by par[i].
A subset of nodes within the subtree of a node is called good if every digit from 0 to 9 appears at most once in the decimal representation of the values of the selected nodes.
The score of a good subset is the sum of the values of its nodes.
Define an array maxScore of length n, where maxScore[u] represents the maximum possible sum of values of a good subset of nodes that belong to the subtree rooted at node u, including u itself and all its descendants.
Return the sum of all values in maxScore.
Since the answer may be large, return it modulo 109 + 7.
Example 1:
Input: vals = [2,3], par = [-1,0]
Output: 8
Explanation:
- The subtree rooted at node 0 includes nodes
{0, 1}. The subset{2, 3}is good as the digits 2 and 3 appear only once. The score of this subset is2 + 3 = 5. - The subtree rooted at node 1 includes only node
{1}. The subset{3}is good. The score of this subset is 3. - The
maxScorearray is[5, 3], and the sum of all values inmaxScoreis5 + 3 = 8. Thus, the answer is 8.
Example 2:
Input: vals = [1,5,2], par = [-1,0,0]
Output: 15
Explanation:
- The subtree rooted at node 0 includes nodes
{0, 1, 2}. The subset{1, 5, 2}is good as the digits 1, 5 and 2 appear only once. The score of this subset is1 + 5 + 2 = 8. - The subtree rooted at node 1 includes only node
{1}. The subset{5}is good. The score of this subset is 5. - The subtree rooted at node 2 includes only node
{2}. The subset{2}is good. The score of this subset is 2. - The
maxScorearray is[8, 5, 2], and the sum of all values inmaxScoreis8 + 5 + 2 = 15. Thus, the answer is 15.
Example 3:
Input: vals = [34,1,2], par = [-1,0,1]
Output: 42
Explanation:
- The subtree rooted at node 0 includes nodes
{0, 1, 2}. The subset{34, 1, 2}is good as the digits 3, 4, 1 and 2 appear only once. The score of this subset is34 + 1 + 2 = 37. - The subtree rooted at node 1 includes node
{1, 2}. The subset{1, 2}is good as the digits 1 and 2 appear only once. The score of this subset is1 + 2 = 3. - The subtree rooted at node 2 includes only node
{2}. The subset{2}is good. The score of this subset is 2. - The
maxScorearray is[37, 3, 2], and the sum of all values inmaxScoreis37 + 3 + 2 = 42. Thus, the answer is 42.
Example 4:
Input: vals = [3,22,5], par = [-1,0,1]
Output: 18
Explanation:
- The subtree rooted at node 0 includes nodes
{0, 1, 2}. The subset{3, 22, 5}is not good, as digit 2 appears twice. Therefore, the subset{3, 5}is valid. The score of this subset is3 + 5 = 8. - The subtree rooted at node 1 includes nodes
{1, 2}. The subset{22, 5}is not good, as digit 2 appears twice. Therefore, the subset{5}is valid. The score of this subset is 5. - The subtree rooted at node 2 includes
{2}. The subset{5}is good. The score of this subset is 5. - The
maxScorearray is[8, 5, 5], and the sum of all values inmaxScoreis8 + 5 + 5 = 18. Thus, the answer is 18.
Constraints:
1 <= n == vals.length <= 5001 <= vals[i] <= 109par.length == npar[0] == -10 <= par[i] < nforiin[1, n - 1]- The input is generated such that the parent array
parrepresents a valid tree.
Approach Overview
Problem Overview: You are given a tree where each node contributes to a score. A subtree is considered good only if it satisfies a constraint on the values inside the subtree (typically uniqueness or non‑overlapping value sets). The task is to explore all possible subtrees and return the maximum score among those that remain valid.
Approach 1: Brute Force Subtree Validation (O(n^2) time, O(n) space)
The most direct idea is to treat every node as the root of a subtree and explicitly collect all nodes beneath it using a DFS. For each collected subtree, iterate through its values and check whether the constraint (such as uniqueness) holds. If the subtree is valid, compute its score and update the global maximum. This approach repeatedly traverses overlapping portions of the tree, which pushes the complexity to roughly O(n^2) in the worst case. It works for small trees but becomes slow when the tree is large.
Approach 2: DFS + Bitmask Dynamic Programming (O(n) time, O(n) space)
The efficient solution processes the tree in a single depth‑first traversal using a bottom‑up strategy. Each DFS call returns a bitmask representing the set of values present in that subtree along with the accumulated score. While merging results from children, check for conflicts using a bitwise AND operation. If two masks overlap, the subtree is invalid and should be discarded. Otherwise combine them using bitwise OR and add the scores. Because bit operations are constant time and every node is processed once, the overall complexity becomes O(n) with O(n) recursion space.
This method is a common pattern when solving tree problems with value constraints. A compact bit representation avoids expensive set operations and allows quick conflict detection. The traversal itself relies on classic Depth-First Search, while the state merging resembles Dynamic Programming on trees. The value tracking is implemented with bitmask operations.
Recommended for interviews: Interviewers expect the DFS + bitmask approach. The brute force version shows you understand subtree enumeration, but the optimized solution demonstrates stronger algorithmic thinking by compressing subtree state and merging results in linear time.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subtree Validation | O(n^2) | O(n) | Useful for understanding subtree enumeration or when constraints are very small |
| DFS + Bitmask Dynamic Programming | O(n) | O(n) | General optimal solution for large trees with uniqueness or set constraints |