Smallest Missing Genetic Value in Each Subtree — LeetCode 2003 Python Solution
HardTreeDepth-First SearchUnion FindDynamic Programming
- Problem
- #2003
- Pattern
- Union-Find
- 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
Python
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
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) auxiliary |
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
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.