Skip to content

2003. Smallest Missing Genetic Value in Each Subtree 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
 public:
  vector<int> smallestMissingValueSubtree(vector<int>& parents,
                                          vector<int>& nums) {
    const int n = parents.size();
    vector<int> ans(n, 1);
    vector<vector<int>> tree(n);
    unordered_set<int> seen;
    int minMiss = 1;

    for (int i = 1; i < n; ++i)
      tree[parents[i]].push_back(i);

    int nodeThatsOne = getNode(nums);
    if (nodeThatsOne == -1)
      return ans;

    int u = nodeThatsOne;
    int prev = -1;  // the u that just handled

    // Upward from `nodeThatsOne` to the root `u`.
    while (u != -1) {
      for (const int v : tree[u])
        if (v != prev)
          dfs(v, tree, seen, nums);
      seen.insert(nums[u]);
      while (seen.contains(minMiss))
        ++minMiss;
      ans[u] = minMiss;
      prev = u;
      u = parents[u];
    }

    return ans;
  }

 private:
  int getNode(const vector<int>& nums) {
    for (int i = 0; i < nums.size(); ++i)
      if (nums[i] == 1)
        return i;
    return -1;
  }

  void dfs(int u, const vector<vector<int>>& tree, unordered_set<int>& seen,
           const vector<int>& nums) {
    seen.insert(nums[u]);
    for (const int v : tree[u])
      dfs(v, tree, seen, nums);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
  public int[] smallestMissingValueSubtree(int[] parents, int[] nums) {
    final int n = parents.length;
    int[] ans = new int[n];
    Arrays.fill(ans, 1);
    List<Integer>[] tree = new List[n];
    Set<Integer> seen = new HashSet<>();
    int minMiss = 1;

    for (int i = 0; i < n; ++i)
      tree[i] = new ArrayList<>();

    for (int i = 1; i < n; ++i)
      tree[parents[i]].add(i);

    final int nodeThatsOne = getNode(nums);
    if (nodeThatsOne == -1)
      return ans;

    int u = nodeThatsOne;
    int prev = -1; // the u that just handled

    // Upward from `nodeThatsOne` to the root `u`.
    while (u != -1) {
      for (final int v : tree[u])
        if (v != prev)
          dfs(v, tree, seen, nums);
      seen.add(nums[u]);
      while (seen.contains(minMiss))
        ++minMiss;
      ans[u] = minMiss;
      prev = u;
      u = parents[u];
    }

    return ans;
  }

  private void dfs(int u, List<Integer>[] tree, Set<Integer> seen, int[] nums) {
    seen.add(nums[u]);
    for (final int v : tree[u])
      dfs(v, tree, seen, nums);
  }

  private int getNode(int[] nums) {
    for (int i = 0; i < nums.length; ++i)
      if (nums[i] == 1)
        return i;
    return -1;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution:
  def smallestMissingValueSubtree(
      self,
      parents: list[int],
      nums: list[int],
  ) -> list[int]:
    n = len(parents)
    ans = [1] * n
    tree = [[] for _ in range(n)]
    seen = set()
    minMiss = 1

    for i in range(1, n):
      tree[parents[i]].append(i)

    def getNode(nums: list[int]) -> int:
      for i, num in enumerate(nums):
        if num == 1:
          return i
      return -1

    nodeThatsOne = getNode(nums)
    if nodeThatsOne == -1:
      return ans

    u = nodeThatsOne
    prev = -1  # the u that just handled

    def dfs(u: int) -> None:
      seen.add(nums[u])
      for v in tree[u]:
        dfs(v)

    # Upward from `nodeThatsOne` to the root `u`.
    while u != -1:
      for v in tree[u]:
        if v != prev:
          dfs(v)
      seen.add(nums[u])
      while minMiss in seen:
        minMiss += 1
      ans[u] = minMiss
      prev = u
      u = parents[u]

    return ans