Sum of Perfect Square Ancestors - Video Solutions
Sum of Perfect Square Ancestors | LeetCode 3715 | Tree DP
Sum of Perfect Square Ancestors - Video Solution
Watch 3 video solutions for Sum of Perfect Square Ancestors, a hard level problem involving Array, Hash Table, Math. This walkthrough by Sanyam IIT Guwahati has 958 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given an integer n and an undirected tree rooted at node 0 with n nodes numbered from 0 to n - 1. This is represented by a 2D array edges of length n - 1, where edges[i] = [ui, vi] indicates an undirected edge between nodes ui and vi.
You are also given an integer array nums, where nums[i] is the positive integer assigned to node i.
Define a value ti as the number of ancestors of node i such that the product nums[i] * nums[ancestor] is a perfect square.
Return the sum of all ti values for all nodes i in range [1, n - 1].
Note:
- In a rooted tree, the ancestors of node
iare all nodes on the path from nodeito the root node 0, excludingiitself.
Example 1:
Input: n = 3, edges = [[0,1],[1,2]], nums = [2,8,2]
Output: 3
Explanation:
i |
Ancestors | nums[i] * nums[ancestor] |
Square Check | ti |
|---|---|---|---|---|
| 1 | [0] | nums[1] * nums[0] = 8 * 2 = 16 |
16 is a perfect square | 1 |
| 2 | [1, 0] | nums[2] * nums[1] = 2 * 8 = 16nums[2] * nums[0] = 2 * 2 = 4 |
Both 4 and 16 are perfect squares | 2 |
Thus, the total number of valid ancestor pairs across all non-root nodes is 1 + 2 = 3.
Example 2:
Input: n = 3, edges = [[0,1],[0,2]], nums = [1,2,4]
Output: 1
Explanation:
i |
Ancestors | nums[i] * nums[ancestor] |
Square Check | ti |
|---|---|---|---|---|
| 1 | [0] | nums[1] * nums[0] = 2 * 1 = 2 |
2 is not a perfect square | 0 |
| 2 | [0] | nums[2] * nums[0] = 4 * 1 = 4 |
4 is a perfect square | 1 |
Thus, the total number of valid ancestor pairs across all non-root nodes is 1.
Example 3:
Input: n = 4, edges = [[0,1],[0,2],[1,3]], nums = [1,2,9,4]
Output: 2
Explanation:
i |
Ancestors | nums[i] * nums[ancestor] |
Square Check | ti |
|---|---|---|---|---|
| 1 | [0] | nums[1] * nums[0] = 2 * 1 = 2 |
2 is not a perfect square | 0 |
| 2 | [0] | nums[2] * nums[0] = 9 * 1 = 9 |
9 is a perfect square | 1 |
| 3 | [1, 0] | nums[3] * nums[1] = 4 * 2 = 8nums[3] * nums[0] = 4 * 1 = 4 |
Only 4 is a perfect square | 1 |
Thus, the total number of valid ancestor pairs across all non-root nodes is 0 + 1 + 1 = 2.
Constraints:
1 <= n <= 105edges.length == n - 1edges[i] = [ui, vi]0 <= ui, vi <= n - 1nums.length == n1 <= nums[i] <= 105- The input is generated such that
edgesrepresents a valid tree.
Approach Overview
Problem Overview: You are given a tree where each node contains an integer value. For every node, consider its ancestors along the path to the root. The task is to accumulate the contribution of ancestors whose values are perfect squares and compute the required total efficiently.
Approach 1: Brute Force Ancestor Traversal (O(n^2) time, O(h) space)
The direct method checks every node and walks upward through its ancestor chain. For each ancestor, test whether the value is a perfect square using sqrt(x) and verify r * r == x. If the check passes, include it in the running sum. In the worst case (a skewed tree), each node scans up to n ancestors, giving O(n^2) time and O(h) recursion or stack space. This approach is useful for understanding the requirement but quickly becomes too slow for large trees.
Approach 2: DFS with Running Perfect-Square Count (O(n) time, O(h) space)
A more efficient strategy processes the tree using Depth-First Search. While traversing from root to leaves, maintain the contribution from ancestors that are perfect squares. At each node, check whether its value is a square using a constant-time number theory test (int r = sqrt(val)). If it is, update the running sum before exploring children. Each node receives the accumulated value from its parent and passes an updated value to its children. Because each node is visited once and ancestor information is carried forward instead of recomputed, the algorithm runs in O(n) time with O(h) recursion depth.
Approach 3: DFS with Hash Tracking and Number Theory Precheck (O(n) time, O(h) space)
If node values repeat frequently, you can cache square checks in a hash table. Before traversal, determine whether each unique value is a perfect square and store the result. During DFS, look up the value instead of recomputing the square root. This removes repeated math operations and helps when value ranges are large. The traversal logic stays the same: maintain the running ancestor contribution while descending the tree. Concepts from number theory ensure that the square check remains constant time.
Recommended for interviews: The DFS propagation approach is what interviewers expect. It shows that you understand tree traversal, path state propagation, and how to avoid recomputing ancestor relationships. Mentioning the brute force solution demonstrates baseline reasoning, but the optimized DFS solution proves you can reduce repeated work and achieve linear time.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Ancestor Traversal | O(n^2) | O(h) | Small trees or initial reasoning during interviews |
| DFS with Running Perfect-Square Count | O(n) | O(h) | General optimal solution for most constraints |
| DFS with Hash Cached Square Checks | O(n) | O(h + u) | When node values repeat and avoiding repeated sqrt checks improves performance |