HardNo. 2003
Smallest Missing Genetic Value in Each Subtree — LeetCode 2003 Python Solution
- Pattern
- Union-Find
- Topics
- Tree, Depth-First Search, Union Find, Dynamic Programming
- Reading time
- 6 min
- Source
- leetcode.com
The problem
There is a family tree rooted at 0 consisting of n nodes numbered 0 to n - 1. You are given a 0-indexed integer array parents, where parents[i] is the parent for node i.
Example
- Input
- parents = [-1,0,0,2], nums = [1,2,3,4]
- Output
- [5,1,1,1]
- Explanation
- The answer for each subtree is calculated as follows:
Python solution
class Solution:
def smallestMissingValueSubtree(
self, parents: List[int], nums: List[int]
) -> List[int]:
def dfs(i: int):
if vis[i]:
return
vis[i] = True
if nums[i] < len(has):
has[nums[i]] = True
for j in g[i]:
dfs(j)
n = len(nums)
ans = [1] * n
g = [[] for _ in range(n)]
idx = -1
for i, p in enumerate(parents):
if i:
g[p].append(i)
if nums[i] == 1:
idx = i
if idx == -1:
return ans
vis = [False] * n
has = [False] * (n + 2)
i = 2
while idx != -1:
dfs(idx)
while has[i]:
i += 1
ans[idx] = i
idx = parents[idx]
return ansComplexity
- Time
- O(n)
- Space · auxiliary
- O(n)
Pattern: Union-Find
Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 2003. Smallest Missing Genetic Value in Each Subtree is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.
The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0124 | Binary Tree Maximum Path Sum | Hard |
| 0337 | House Robber III | Medium |
| 0834 | Sum of Distances in Tree | Hard |
| 0968 | Binary Tree Cameras | Hard |
| 1372 | Longest ZigZag Path in a Binary Tree | Medium |
| 1373 | Maximum Sum BST in Binary Tree | Hard |
Frequently asked questions
- How hard is LeetCode 2003. Smallest Missing Genetic Value in Each Subtree?
LeetCode 2003. Smallest Missing Genetic Value in Each Subtree is rated Hard on LeetCode.
- What is the time complexity of LeetCode 2003. Smallest Missing Genetic Value in Each Subtree?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 2003. Smallest Missing Genetic Value in Each Subtree?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 2003. Smallest Missing Genetic Value in Each Subtree cover?
LeetCode 2003. Smallest Missing Genetic Value in Each Subtree is tagged Tree, Depth-First Search, Union Find and Dynamic Programming on LeetCode.