Skip to main content
Talentd

Maximum Good Subtree Score - Solution & Explanation

HardArrayDynamic ProgrammingBit ManipulationTree6 min readAsked at: Infosys
Practice this problem

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 is 2 + 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 maxScore array is [5, 3], and the sum of all values in maxScore is 5 + 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 is 1 + 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 maxScore array is [8, 5, 2], and the sum of all values in maxScore is 8 + 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 is 34 + 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 is 1 + 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 maxScore array is [37, 3, 2], and the sum of all values in maxScore is 37 + 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 is 3 + 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 maxScore array is [8, 5, 5], and the sum of all values in maxScore is 8 + 5 + 5 = 18. Thus, the answer is 18.

 

Constraints:

  • 1 <= n == vals.length <= 500
  • 1 <= vals[i] <= 109
  • par.length == n
  • par[0] == -1
  • 0 <= par[i] < n for i in [1, n - 1]
  • The input is generated such that the parent array par represents 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.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Subtree ValidationO(n^2)O(n)Useful for understanding subtree enumeration or when constraints are very small
DFS + Bitmask Dynamic ProgrammingO(n)O(n)General optimal solution for large trees with uniqueness or set constraints

Video Solution

3575. Maximum Good Subtree Score | Leetcode Biweekly Contest 158 • Amit Dhyani • 570 views views

Watch 3 more video solutions →

Frequently Asked Questions

Is Maximum Good Subtree Score easy or hard?
Maximum Good Subtree Score is categorized as a Hard problem because it combines tree traversal, dynamic programming on trees, and bitmask optimization. The challenge lies in designing a compact state representation and correctly merging subtree results.
Maximum Good Subtree Score Python/Java solution
Implement a recursive DFS that returns a pair containing a bitmask and the subtree score. Python, Java, C++, and Go implementations follow the same logic: traverse children, combine masks with bitwise operations, and track the maximum valid score.
How to solve Maximum Good Subtree Score in O(n)?
Perform a post‑order DFS where each node returns a bitmask representing values in its subtree and the corresponding score. While merging children results, detect conflicts using mask & mask checks. If no overlap exists, combine masks with OR and update the maximum score.
What is the best approach for Maximum Good Subtree Score?
The most efficient approach uses a DFS traversal combined with bitmask dynamic programming. Each subtree returns a bitmask representing the values inside it, and masks are merged while checking conflicts using bitwise AND. This avoids repeated subtree scans and computes the maximum score in linear time.
Is Maximum Good Subtree Score asked at Google/Amazon/Meta?
Tree dynamic programming and bitmask merging patterns commonly appear in interviews at companies like Google, Amazon, and Meta. Variations of subtree validation problems are frequently used to test DFS reasoning and state compression techniques.
What data structure is used in Maximum Good Subtree Score?
The core structure is a tree represented with adjacency lists, explored using depth‑first search. Bitmasks store the set of values inside each subtree, enabling fast conflict detection and merging operations.
What is the time complexity of Maximum Good Subtree Score?
The optimal DFS + bitmask solution runs in O(n) time where n is the number of nodes in the tree. Each node is visited exactly once and bitwise operations are constant time. Space complexity is O(n) due to recursion depth and temporary state.

Ready to solve this problem?

Practice Maximum Good Subtree Score with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays