Smallest Missing Genetic Value in Each Subtree solution and explanation
4 more videos on this problem
LeetCode 2003. Smallest Missing Genetic Value in Each SubtreeHappy Coding · 17:15 · 1K views
【每日一题】LeetCode 2003. Smallest Missing Genetic Value in Each Subtree, 9/19/2021Huifeng Guan · 59:39 · 731 views
Leetcode 2003. Smallest Missing Genetic Value in Each Subtree | LeetcodeA Code Daily! · 12:53 · 709 views
2003. Smallest Missing Genetic Value in Each Subtree (Leetcode Hard)Programming Live with Larry · 43:47 · 604 views
LeetCode 2003: Smallest Missing Genetic Value in Each SubtreeAlitaCode · 31:11 · 13 views
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. Since node 0 is the root, parents[0] == -1.
There are 105 genetic values, each represented by an integer in the inclusive range [1, 105]. You are given a 0-indexed integer array nums, where nums[i] is a distinct genetic value for node i.
Return an array ans of length n where ans[i] is the smallest genetic value that is missing from the subtree rooted at node i.
The subtree rooted at a node x contains node x and all of its descendant nodes.
Example 1:
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: - 0: The subtree contains nodes [0,1,2,3] with values [1,2,3,4]. 5 is the smallest missing value. - 1: The subtree contains only node 1 with value 2. 1 is the smallest missing value. - 2: The subtree contains nodes [2,3] with values [3,4]. 1 is the smallest missing value. - 3: The subtree contains only node 3 with value 4. 1 is the smallest missing value.
Example 2:
Input: parents = [-1,0,1,0,3,3], nums = [5,4,6,2,1,3] Output: [7,1,1,4,2,1] Explanation: The answer for each subtree is calculated as follows: - 0: The subtree contains nodes [0,1,2,3,4,5] with values [5,4,6,2,1,3]. 7 is the smallest missing value. - 1: The subtree contains nodes [1,2] with values [4,6]. 1 is the smallest missing value. - 2: The subtree contains only node 2 with value 6. 1 is the smallest missing value. - 3: The subtree contains nodes [3,4,5] with values [2,1,3]. 4 is the smallest missing value. - 4: The subtree contains only node 4 with value 1. 2 is the smallest missing value. - 5: The subtree contains only node 5 with value 3. 1 is the smallest missing value.
Example 3:
Input: parents = [-1,2,3,0,2,4,1], nums = [2,3,4,5,6,7,8] Output: [1,1,1,1,1,1,1] Explanation: The value 1 is missing from all the subtrees.
Constraints:
n == parents.length == nums.length2 <= n <= 1050 <= parents[i] <= n - 1fori != 0parents[0] == -1parentsrepresents a valid tree.1 <= nums[i] <= 105- Each
nums[i]is distinct.
Approach overview
Problem Overview: You are given a rooted tree where each node has a unique genetic value. For every node, compute the smallest positive genetic value that does not appear in its subtree. The challenge is efficiently tracking which values exist inside each subtree without recomputing sets from scratch.
Approach 1: DFS with a Set to Track Genetic Values (O(n^2) worst-case time, O(n) space)
This method performs a depth-first search and builds a set of genetic values for each subtree. When DFS visits a node, it recursively collects the sets from its children and merges them into the current node’s set. After merging, iterate from value 1 upward until you find the smallest number not present in the set. That value becomes the answer for the current node. The key operation is merging child sets and performing hash lookups to detect missing values. This approach is easy to implement and clearly demonstrates subtree aggregation, but repeated set merges can degrade to O(n^2) time in skewed trees.
Approach 2: Union-Find with Path Compression (O(n α(n)) time, O(n) space)
This optimized strategy uses a Union-Find structure combined with subtree traversal. The core observation: only nodes along the path from the node containing genetic value 1 up to the root can have answers greater than 1. All other subtrees are missing value 1. Starting from the node that contains value 1, move upward toward the root while progressively marking nodes in each subtree as visited using DFS. Each visited genetic value is unioned with the next value, effectively tracking the next available missing integer using path compression. The smallest missing value for the current subtree is found by querying the next unconnected number. This avoids rebuilding sets and ensures near-linear complexity.
The solution heavily relies on properties of tree traversal. Subtrees can be explored independently, and the genetic value constraint allows efficient detection of missing integers once values are marked.
Recommended for interviews: The Union-Find optimization is the approach most interviewers expect for this Hard problem. It demonstrates deeper insight into subtree structure and missing-number tracking. Implementing the DFS + set approach first can show your reasoning process, but the optimized Union-Find method proves you can reduce redundant work and reach near-linear complexity.
Approach 1: DFS with a Set to Track Genetic Values
This approach utilizes depth-first search (DFS) to traverse the tree and a set to track genetic values in each subtree. By doing this, you can efficiently identify the smallest missing genetic value.
def smallestMissingValueSubtree(parents, nums):
from collections import defaultdict
def dfs(node):
visited[node] = True
current_genetic_values.add(nums[node])
for child in children[node]:
if not visited[child]:
dfs(child)
n = len(nums)
children = defaultdict(list)
for i in range(1, n):
children[parents[i]].append(i)
result = [1] * n
visited = [False] * n
current_genetic_values = set()
for i in range(n):
if not visited[i]:
current_genetic_values.clear()
dfs(i)
for j in range(1, n + 2): # n + 1 is the max possible genetic value
if j not in current_genetic_values:
result[i] = j
break
return result
#include <vector>
#include <unordered_set>
#include <unordered_map>
using namespace std;
class Solution {
public:
void dfs(int node, vector<int>& nums, vector<vector<int>>& children, unordered_set<int>& genetic_set) {
genetic_set.insert(nums[node]);
for (int child : children[node]) {
dfs(child, nums, children, genetic_set);
}
}
vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& nums) {
int n = nums.size();
vector<vector<int>> children(n);
for (int i = 1; i < n; ++i) {
children[parents[i]].push_back(i);
}
vector<int> result(n, 1);
unordered_set<int> genetic_set;
for (int i = 0; i < n; ++i) {
genetic_set.clear();
dfs(i, nums, children, genetic_set);
int smallest_missing = 1;
while (genetic_set.find(smallest_missing) != genetic_set.end()) {
++smallest_missing;
}
result[i] = smallest_missing;
}
return result;
}
};The code employs DFS to explore each subtree and gather genetic values using a set. The aim is to determine the smallest missing genetic value in each subtree by iterating through possible genetic numbers and checking their presence.
The time complexity is O(n^2), predominantly due to the iterative process over the genetic values up to n+1 in each subtree DFS traversal. The space complexity is O(n) utilized by the data structures to track children and visited nodes.
Approach 2: Union-Find with Path Compression
This method uses a union-find data structure with path compression to efficiently detect the smallest missing genetic value. It focuses on connectivity and quick access to elements in subtrees.
import java.util.*;
public class Solution {
public int[] smallestMissingValueSubtree(int[] parents, int[] nums) {
int n = nums.length;
Map<Integer, List<Integer>> tree = new HashMap<>();
for (int i = 1; i < n; i++) {
tree.computeIfAbsent(parents[i], k -> new ArrayList<>()).add(i);
}
int[] result = new int[n];
Arrays.fill(result, 1);
int smallestMissing = 1;
int[] seen = new int[100002];
Arrays.fill(seen, 0);
for (int i = 0; i < n; i++) {
if (nums[i] == smallestMissing) {
dfs(i, tree, nums, seen);
while (seen[smallestMissing] == 1) smallestMissing++;
}
result[i] = smallestMissing;
}
return result;
}
private void dfs(int node, Map<Integer, List<Integer>> tree, int[] nums, int[] seen) {
seen[nums[node]] = 1;
if (tree.containsKey(node)) {
for (int child : tree.get(node)) {
dfs(child, tree, nums, seen);
}
}
}
}
using System;
using System.Collections.Generic;
public class Solution {
public int[] SmallestMissingValueSubtree(int[] parents, int[] nums) {
int n = nums.Length;
Dictionary<int, List<int>> tree = new Dictionary<int, List<int>>();
for (int i = 1; i < n; i++) {
if (!tree.ContainsKey(parents[i])) {
tree[parents[i]] = new List<int>();
}
tree[parents[i]].Add(i);
}
int[] result = new int[n];
Array.Fill(result, 1);
int smallestMissing = 1;
bool[] seen = new bool[100002];
for (int i = 0; i < n; i++) {
if (nums[i] == smallestMissing) {
Dfs(i, tree, nums, seen);
while (seen[smallestMissing]) smallestMissing++;
}
result[i] = smallestMissing;
}
return result;
}
private void Dfs(int node, Dictionary<int, List<int>> tree, int[] nums, bool[] seen) {
seen[nums[node]] = true;
if (tree.ContainsKey(node)) {
foreach (int child in tree[node]) {
Dfs(child, tree, nums, seen);
}
}
}
}This Java code integrates a DFS traversal with a union-find approach to efficiently trace and flag seen genetic values using an array. This assists in promptly identifying the smallest missing number.
The time complexity is O(n log n) due to union-find operations with path compression, while space complexity is also O(n) due to auxiliary storage usage.
Approach 3: DFS
We notice that each node has a unique gene value, so we only need to find the node idx with gene value 1, and all nodes except for those on the path from node idx to the root node 0 have an answer of 1.
Therefore, we initialize the answer array ans to [1,1,...,1], and our focus is on finding the answer for each node on the path from node idx to the root node 0.
We can start from node idx and use depth-first search to mark the gene values that appear in the subtree rooted at idx, and record them in the array has. During the search process, we use an array vis to mark the visited nodes to prevent repeated visits.
Next, we start from i=2 and keep looking for the first gene value that has not appeared, which is the answer for node idx. Here, i is strictly increasing, because the gene values are unique, so we can always find a gene value that has not appeared in [1,..n+1].
Then, we update the answer for node idx, i.e., ans[idx]=i, and update idx to its parent node to continue the above process until idx=-1, which means we have reached the root node 0.
Finally, we return the answer array ans.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes.
function smallestMissingValueSubtree(parents: number[], nums: number[]): number[] {
const n = nums.length;
const g: number[][] = Array.from({ length: n }, () => []);
const vis: boolean[] = Array(n).fill(false);
const has: boolean[] = Array(n + 2).fill(false);
const ans: number[] = Array(n).fill(1);
let idx = -1;
for (let i = 0; i < n; ++i) {
if (i) {
g[parents[i]].push(i);
}
if (nums[i] === 1) {
idx = i;
}
}
if (idx === -1) {
return ans;
}
const dfs = (i: number): void => {
if (vis[i]) {
return;
}
vis[i] = true;
if (nums[i] < has.length) {
has[nums[i]] = true;
}
for (const j of g[i]) {
dfs(j);
}
};
for (let i = 2; ~idx; idx = parents[idx]) {
dfs(idx);
while (has[i]) {
++i;
}
ans[idx] = i;
}
return ans;
}func smallestMissingValueSubtree(parents []int, nums []int) []int {
n := len(nums)
g := make([][]int, n)
vis := make([]bool, n)
has := make([]bool, n+2)
idx := -1
ans := make([]int, n)
for i, p := range parents {
if i > 0 {
g[p] = append(g[p], i)
}
if nums[i] == 1 {
idx = i
}
ans[i] = 1
}
if idx < 0 {
return ans
}
var dfs func(int)
dfs = func(i int) {
if vis[i] {
return
}
vis[i] = true
if nums[i] < len(has) {
has[nums[i]] = true
}
for _, j := range g[i] {
dfs(j)
}
}
for i := 2; idx != -1; idx = parents[idx] {
dfs(idx)
for has[i] {
i++
}
ans[idx] = i
}
return ans
}impl Solution {
pub fn smallest_missing_value_subtree(parents: Vec<i32>, nums: Vec<i32>) -> Vec<i32> {
fn dfs(
i: usize,
vis: &mut Vec<bool>,
has: &mut Vec<bool>,
g: &Vec<Vec<usize>>,
nums: &Vec<i32>,
) {
if vis[i] {
return;
}
vis[i] = true;
if nums[i] < (has.len() as i32) {
has[nums[i] as usize] = true;
}
for &j in &g[i] {
dfs(j, vis, has, g, nums);
}
}
let n = nums.len();
let mut ans = vec![1; n];
let mut g: Vec<Vec<usize>> = vec![vec![]; n];
let mut idx = -1;
for (i, &p) in parents.iter().enumerate() {
if i > 0 {
g[p as usize].push(i);
}
if nums[i] == 1 {
idx = i as i32;
}
}
if idx == -1 {
return ans;
}
let mut vis = vec![false; n];
let mut has = vec![false; (n + 2) as usize];
let mut i = 2;
let mut idx_mut = idx;
while idx_mut != -1 {
dfs(idx_mut as usize, &mut vis, &mut has, &g, &nums);
while has[i] {
i += 1;
}
ans[idx_mut as usize] = i as i32;
idx_mut = parents[idx_mut as usize];
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| DFS with a Set to Track Genetic Values | The time complexity is O(n^2), predominantly due to the iterative process over the genetic values up to n+1 in each subtree DFS traversal. The space complexity is O(n) utilized by the data structures to track children and visited nodes. |
| Union-Find with Path Compression | The time complexity is O(n log n) due to union-find operations with path compression, while space complexity is also O(n) due to auxiliary storage usage. |
| DFS | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS with Set Tracking | O(n^2) worst case | O(n) | Good for understanding subtree aggregation and quick prototyping |
| Union-Find with Path Compression | O(n α(n)) | O(n) | Optimal solution for large trees and interview settings |
Frequently asked questions
Is Smallest Missing Genetic Value in Each Subtree easy or hard?
LeetCode classifies this problem as Hard because it combines tree traversal, missing-number tracking, and optimization techniques. The naive DFS approach is straightforward, but achieving near-linear time requires deeper insight using Union-Find and subtree observations.
Smallest Missing Genetic Value in Each Subtree Python/Java solution
Python and C++ implementations typically use DFS with sets or optimized traversal logic. Java and C# solutions often use Union-Find structures to track the next available missing genetic value. All implementations rely on subtree traversal and efficient value tracking.
How to solve Smallest Missing Genetic Value in Each Subtree in O(n)?
Use the observation that only nodes on the path from the node containing genetic value 1 to the root can have answers greater than 1. Traverse this path upward, perform DFS to mark values in each subtree, and maintain the smallest missing number using Union-Find or a pointer that skips already-seen values. This ensures each node and value is processed once.
What is the best approach for Smallest Missing Genetic Value in Each Subtree?
The most efficient approach uses Union-Find with path compression combined with DFS traversal. The algorithm starts from the node containing genetic value 1 and moves upward toward the root while marking subtree values as visited. This avoids rebuilding sets for every subtree and achieves near-linear time complexity of O(n α(n)).
Is Smallest Missing Genetic Value in Each Subtree asked at Google/Amazon/Meta?
Tree and union-find problems with subtree queries frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of missing-number tracking in trees and DFS aggregation are common in system design and algorithm rounds.
What data structure is used in Smallest Missing Genetic Value in Each Subtree?
Key data structures include adjacency lists for representing the tree, hash sets for tracking genetic values in simpler solutions, and Union-Find with path compression for the optimal implementation. DFS traversal is used to explore each subtree efficiently.
What is the time complexity of Smallest Missing Genetic Value in Each Subtree?
The optimal solution runs in O(n α(n)) time using Union-Find with path compression, where α(n) is the inverse Ackermann function and effectively constant. A simpler DFS approach that merges sets can degrade to O(n^2) in the worst case due to repeated set merging.