Smallest missing genetic value in each subtree

Array Dynamic Programming Tree Depth-First Search Union-Find

47.7% acceptance

Feb 25, 2026

487

You are given an integer n and a 0-indexed integer array parents of length n where parents[i] is the parent of node i in the tree (0-indexed). Additionally, you are given a 0-indexed integer array nums of length n where nums[i] is a distinct value associated with node i. Return an array ans of length n where ans[i] is the smallest missing positive integer that is not present in the subtree rooted at node i.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn smallest_missing_value_subtree(parents: Vec<i32>, nums: Vec<i32>) -> Vec<i32> {
    let n = parents.len();
    let mut ans = vec![1i32; n];
    
    // Find which node has value 1
    let node_with_one = nums.iter().position(|&v| v == 1);
    if node_with_one.is_none() {
      return ans;
    }
    
    // Build children list
    let mut children: Vec<Vec<usize>> = vec![vec![]; n];
    for i in 1..n {
      children[parents[i] as usize].push(i);
    }
    
    // DFS to collect all values in each subtree (only path from node_with_one to root matters)
    // Walk up from node_with_one to root, keeping a set
    let mut visited = vec![false; n];
    let mut seen: std::collections::HashSet<i32> = std::collections::HashSet::new();
    let mut missing = 1i32;
    
    // We need to do DFS for each node on path from node_with_one to root
    // For other nodes, answer is 1
    let mut path = vec![];
    let mut cur = node_with_one.unwrap();
    loop {
      path.push(cur);
      if cur == 0 { break; }
      cur = parents[cur] as usize;
    }
    
    // For each node in path (from node_with_one to root),
    // collect all subtree values via DFS
    // We do it cumulatively: add the subtree of each path node
    
    fn dfs(node: usize, children: &Vec<Vec<usize>>, nums: &Vec<i32>, 
         visited: &mut Vec<bool>, seen: &mut std::collections::HashSet<i32>) {
      if visited[node] { return; }
      visited[node] = true;
      seen.insert(nums[node]);
      for &c in &children[node] {
        dfs(c, children, nums, visited, seen);
      }
    }
    
    for i in 0..path.len() {
      let node = path[i];
      // Add this node and all its subtree children not yet visited
      dfs(node, &children, &nums, &mut visited, &mut seen);
      while seen.contains(&missing) {
        missing += 1;
      }
      ans[node] = missing;
    }
    
    ans
  }
}