Smallest Missing Genetic Value in Each Subtree

hard tree dfs union find

Problem

A rooted tree on n nodes is given by parents (with parents[0] = -1). Each node i has a distinct genetic value nums[i] in [1, 10^5]. For every node, return the smallest positive integer that is missing from the set of genetic values in its subtree.

Inputparents = [-1,0,0,2], nums = [1,2,3,4]

Output[5,1,1,1]

The whole tree (rooted at 0) holds {1,2,3,4}, so its smallest missing value is 5. No other subtree contains value 1, so each is missing 1.

parents array

nums array

def smallest_missing(parents, nums):
    n = len(parents)
    ans = [1] * n
    children = [[] for _ in range(n)]
    for i in range(1, n):
        children[parents[i]].append(i)
    node = nums.index(1) if 1 in nums else -1
    if node == -1:
        return ans
    seen = set()
    missing = 1
    def collect(x):
        stack = [x]
        while stack:
            u = stack.pop()
            if u in visited:
                continue
            visited.add(u)
            seen.add(nums[u])
            stack.extend(children[u])
    visited = set()
    while node != -1:
        collect(node)
        while missing in seen:
            missing += 1
        ans[node] = missing
        node = parents[node]
    return ans

function smallestMissing(parents, nums) {
  const n = parents.length;
  const ans = new Array(n).fill(1);
  const children = Array.from({length: n}, () => []);
  for (let i = 1; i < n; i++) children[parents[i]].push(i);
  let node = nums.indexOf(1);
  if (node === -1) return ans;
  const seen = new Set(), visited = new Set();
  let missing = 1;
  function collect(x) {
    const stack = [x];
    while (stack.length) {
      const u = stack.pop();
      if (visited.has(u)) continue;
      visited.add(u);
      seen.add(nums[u]);
      for (const c of children[u]) stack.push(c);
    }
  }
  while (node !== -1) {
    collect(node);
    while (seen.has(missing)) missing++;
    ans[node] = missing;
    node = parents[node];
  }
  return ans;
}

import java.util.*;
class Solution {
    public int[] smallestMissingValueSubtree(int[] parents, int[] nums) {
        int n = parents.length;
        int[] ans = new int[n]; Arrays.fill(ans, 1);
        List<Integer>[] children = new List[n];
        for (int i = 0; i < n; i++) children[i] = new ArrayList<>();
        for (int i = 1; i < n; i++) children[parents[i]].add(i);
        int node = -1;
        for (int i = 0; i < n; i++) if (nums[i] == 1) node = i;
        if (node == -1) return ans;
        Set<Integer> seen = new HashSet<>(), visited = new HashSet<>();
        int missing = 1;
        while (node != -1) {
            Deque<Integer> stack = new ArrayDeque<>(); stack.push(node);
            while (!stack.isEmpty()) {
                int u = stack.pop();
                if (!visited.add(u)) continue;
                seen.add(nums[u]);
                for (int c : children[u]) stack.push(c);
            }
            while (seen.contains(missing)) missing++;
            ans[node] = missing;
            node = parents[node];
        }
        return ans;
    }
}

class Solution {
public:
    vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& nums) {
        int n = parents.size();
        vector<int> ans(n, 1);
        vector<vector<int>> children(n);
        for (int i = 1; i < n; i++) children[parents[i]].push_back(i);
        int node = -1;
        for (int i = 0; i < n; i++) if (nums[i] == 1) node = i;
        if (node == -1) return ans;
        unordered_set<int> seen, visited;
        int missing = 1;
        while (node != -1) {
            vector<int> stack = {node};
            while (!stack.empty()) {
                int u = stack.back(); stack.pop_back();
                if (!visited.insert(u).second) continue;
                seen.insert(nums[u]);
                for (int c : children[u]) stack.push_back(c);
            }
            while (seen.count(missing)) missing++;
            ans[node] = missing;
            node = parents[node];
        }
        return ans;
    }
};

Explanation

The smallest missing value of a subtree is always at least 1, and it can only be larger than 1 if that subtree actually contains the value 1. Any subtree without value 1 is missing 1 immediately, so we initialize every answer to 1.

The only nodes whose subtree contains 1 are the node holding value 1 and all of its ancestors. So we find that node and walk straight up to the root, computing answers only along this single path.

As we move up, each subtree strictly contains the previous one, so the set of values we've seen only grows. We keep one shared seen set and a missing counter. At each node on the path we add any newly reachable subtree values (visiting each node at most once across the whole walk), then advance missing while it is present.

Because every node is added to seen at most once and missing only increases, the total work is linear, even though we look at many subtrees.

Example on parents = [-1,0,0,2], nums = [1,2,3,4]: node 0 holds value 1 and is the root. Its subtree is the whole tree {1,2,3,4}, so its answer is 5; every other subtree lacks value 1, so each answer is 1 → [5,1,1,1].

Time: O(n) Space: O(n)