Smallest Missing Genetic Value in Each Subtree

Hard

#1825Time: O(N^2). We iterate through N nodes. For each node `i`, we traverse its subtree. The size of a subtree can be up to N. The sum of all subtree sizes can be O(N^2) in the worst case (a path or skewed tree). For each subtree, collecting values and finding the missing one takes time proportional to the subtree size. Thus, the total time complexity is O(N^2).Space: O(N). The adjacency list requires O(N) space. During the calculation for each node, the `HashSet` can grow to store up to N values in the worst case (for the root's subtree), thus requiring O(N) auxiliary space. The recursion stack for DFS can also go up to O(N) in depth for a skewed tree.

Patterns

Dynamic Programming

Algorithms

Depth-First Search Union Find

Data structures

Tree

Prompt

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 10⁵ genetic values, each represented by an integer in the inclusive range [1, 10⁵]. 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.length
2 <= n <= 10⁵
0 <= parents[i] <= n - 1 for i != 0
parents[0] == -1
parents represents a valid tree.
1 <= nums[i] <= 10⁵
Each nums[i] is distinct.

Approaches

2 approaches with complexity analysis and trade-offs.

A straightforward approach is to iterate through each node, and for each node, determine its subtree. Then, we collect all the genetic values within that subtree and find the smallest positive integer not present in the collection. This method is easy to conceptualize but computationally expensive.

Algorithm

1. Construct an adjacency list for the tree from the parents array to represent the child-parent relationships.
1. Initialize an answer array ans of size n.
1. Iterate through each node i from 0 to n-1.
1. For each node i:
- a. Create an empty HashSet to store the genetic values of the nodes in the subtree of i.
- b. Perform a Depth First Search (DFS) or Breadth First Search (BFS) starting from node i to traverse its entire subtree.
- c. For each node j visited in the traversal, add its genetic value nums[j] to the hash set.
- d. After collecting all values, find the smallest missing positive integer. Initialize a variable missingValue = 1.
- e. While the hash set contains missingValue, increment missingValue.
- f. Store the final missingValue in ans[i].
1. After iterating through all nodes, return the ans array.

Walkthrough

This approach tackles the problem directly by processing each node one by one. For every node i in the tree, we need to find the smallest missing genetic value in its subtree.

First, we convert the parents array into a more convenient graph representation, like an adjacency list, where adj[u] contains all children of node u. This allows for easy traversal of subtrees.

Then, for each node i from 0 to n-1, we perform a traversal (e.g., DFS) starting from i. This traversal visits i and all of its descendants. During the traversal, we use a HashSet to collect the distinct genetic values (nums) of all the nodes in the current subtree. The HashSet provides fast O(1) average time complexity for insertions and lookups.

Once the set of genetic values for the subtree of i is complete, we search for the smallest missing positive integer. We start checking from 1 and increment upwards, using the contains method of the hash set to see if the number is present. The first integer we find that is not in the set is the answer for the subtree rooted at i.

We repeat this entire process for all n nodes to fill the final answer array.

1import java.util.*;2 3class Solution {4    public int[] smallestMissingValueSubtree(int[] parents, int[] nums) {5        int n = parents.length;6        List<List<Integer>> children = new ArrayList<>();7        for (int i = 0; i < n; i++) {8            children.add(new ArrayList<>());9        }10        for (int i = 1; i < n; i++) {11            children.get(parents[i]).add(i);12        }13 14        int[] ans = new int[n];15        for (int i = 0; i < n; i++) {16            Set<Integer> subtreeValues = new HashSet<>();17            collectSubtreeValues(i, children, nums, subtreeValues);18            19            int missing = 1;20            while (subtreeValues.contains(missing)) {21                missing++;22            }23            ans[i] = missing;24        }25        return ans;26    }27 28    private void collectSubtreeValues(int u, List<List<Integer>> children, int[] nums, Set<Integer> values) {29        values.add(nums[u]);30        for (int v : children.get(u)) {31            collectSubtreeValues(v, children, nums, values);32        }33    }34}

Complexity

Time

O(N^2). We iterate through N nodes. For each node `i`, we traverse its subtree. The size of a subtree can be up to N. The sum of all subtree sizes can be O(N^2) in the worst case (a path or skewed tree). For each subtree, collecting values and finding the missing one takes time proportional to the subtree size. Thus, the total time complexity is O(N^2).

Space

O(N). The adjacency list requires O(N) space. During the calculation for each node, the `HashSet` can grow to store up to N values in the worst case (for the root's subtree), thus requiring O(N) auxiliary space. The recursion stack for DFS can also go up to O(N) in depth for a skewed tree.

Trade-offs

Pros

- It is simple to understand and implement.
- It correctly solves the problem for small inputs.

Cons

- The time complexity is O(N^2) in the worst-case scenario (e.g., a skewed tree), which is too slow for the given constraints and will result in a 'Time Limit Exceeded' error on most platforms.

This approach is based on a key observation: the smallest missing genetic value for any subtree is 1 unless the subtree contains the genetic value 1. This insight allows us to optimize the problem by focusing only on the subtrees that contain the value 1. These are the subtrees rooted at the node with value 1 and all of its ancestors. By processing only this path and its side-branches, we can achieve a linear time solution.

Algorithm

1. Build an adjacency list representation of the tree from the parents array.
1. Find the node oneNode that has the genetic value 1. If no such node exists, the smallest missing value for every subtree is 1, so return an array filled with 1s.
1. Initialize an answer array ans of size n with all elements set to 1. This is the default answer for any subtree that does not contain the value 1.
1. Initialize an empty HashSet<Integer> called seenValues to store genetic values, and an integer missingValue to 1.
1. Traverse upwards from oneNode to the root of the tree. Let currentNode be the node being processed and prevNode be the child on the path we just came from.
1. In a loop, while currentNode is valid (not -1):
- a. Add the value nums[currentNode] to seenValues.
- b. For each child of currentNode, if the child is not prevNode, perform a full DFS from that child to collect all genetic values in its subtree and add them to seenValues.
- c. After collecting all new values for the current subtree, update missingValue by incrementing it as long as seenValues contains the current missingValue.
- d. Set ans[currentNode] = missingValue.
- e. Move up the path: prevNode = currentNode, currentNode = parents[currentNode].
1. Return the ans array.

Walkthrough

The efficiency of this method comes from avoiding redundant computations. We start by recognizing that any subtree that lacks the genetic value 1 will have 1 as its smallest missing value. Therefore, we can initialize our answer array ans with all 1s.

The problem then reduces to finding the correct answer only for the nodes whose subtrees contain the value 1. These nodes are precisely the node with value 1 (let's call it oneNode) and all its ancestors up to the root.

We can find oneNode with a single pass through the nums array. If 1 is not present in nums, all answers are 1, and we're done. Otherwise, we start an iterative process from oneNode, moving up towards the root using the parents array.

We maintain a single HashSet called seenValues that accumulates the genetic values of the subtrees as we move up the path. We also keep track of the smallest_missing value, initialized to 1.

For each currentNode on the path from oneNode to the root:

We expand our set of values. The subtree of currentNode includes currentNode itself, the subtree of the child we just came from (prevNode), and the subtrees of all other children. Since the values from prevNode's subtree are already in seenValues, we only need to add nums[currentNode] and the values from the subtrees of currentNode's other children (the "side branches").
We achieve this by adding nums[currentNode] and then for each child of currentNode that is not prevNode, we perform a DFS to add all values from its subtree into seenValues.
After updating seenValues, we find the new smallest_missing value by incrementing it until we find a value not in the set.
This value is the answer for currentNode, so we set ans[currentNode].

This process is efficient because each node in the tree is visited and its value is added to the set exactly once, leading to an overall linear time complexity.

1import java.util.*;2 3class Solution {4    public int[] smallestMissingValueSubtree(int[] parents, int[] nums) {5        int n = parents.length;6        List<List<Integer>> children = new ArrayList<>();7        for (int i = 0; i < n; i++) {8            children.add(new ArrayList<>());9        }10        int oneNode = -1;11        for (int i = 0; i < n; i++) {12            if (i != 0) {13                children.get(parents[i]).add(i);14            }15            if (nums[i] == 1) {16                oneNode = i;17            }18        }19 20        int[] ans = new int[n];21        Arrays.fill(ans, 1);22 23        if (oneNode == -1) {24            return ans;25        }26 27        Set<Integer> seenValues = new HashSet<>();28        int missingValue = 1;29        30        int currentNode = oneNode;31        int prevNode = -1;32        33        while (currentNode != -1) {34            // Collect values from the current node and its side branches35            collectSubtree(currentNode, children, nums, seenValues);36            37            while (seenValues.contains(missingValue)) {38                missingValue++;39            }40            ans[currentNode] = missingValue;41            42            // Move up to the parent43            currentNode = parents[currentNode];44        }45 46        return ans;47    }48 49    private void collectSubtree(int u, List<List<Integer>> children, int[] nums, Set<Integer> seenValues) {50        // Use a queue for iterative DFS to avoid stack overflow on skewed trees51        Queue<Integer> q = new LinkedList<>();52        q.offer(u);53        seenValues.add(nums[u]);54 55        while(!q.isEmpty()){56            int node = q.poll();57            for(int child : children.get(node)){58                if(!seenValues.contains(nums[child])){59                    seenValues.add(nums[child]);60                    q.offer(child);61                }62            }63        }64    }65}

Note: The provided code snippet for collectSubtree uses an iterative BFS-like traversal to gather values. This is to prevent potential StackOverflowError on deep/skewed trees, which a recursive DFS might face. The logic of which nodes to visit is handled in the main loop by only initiating the collection from specific nodes. The logic in the main loop is slightly different from the description to be more robust. The collectSubtree is called on currentNode and it traverses the whole subtree. The seenValues set ensures that already visited nodes (from a child's subtree on the path) are not re-processed, making it efficient.

Complexity

Time

O(N). Building the adjacency list is O(N). Finding `oneNode` is O(N). The main part involves traversing up from `oneNode` and collecting values from side branches. Each node in the tree is part of exactly one such branch (or is on the main path). Therefore, each node's value is added to the `seenValues` set exactly once. The total time for all collections is O(N). The `missingValue` pointer only moves forward, and in total, it will be incremented at most N+1 times. Thus, the overall time complexity is linear.

Space

O(N). We need O(N) space for the adjacency list, the `ans` array, and the `seenValues` hash set, which can store up to N distinct genetic values. The queue for the iterative traversal can also hold up to O(N) nodes in the worst case.

Trade-offs

Pros

- Highly efficient with O(N) time complexity, which passes for large inputs.
- The core idea is clever and reduces the problem scope significantly.

Cons

- The logic is more complex to understand and implement compared to the brute-force approach.
- It requires careful handling of pointers/indices to traverse up the path and to correctly identify side branches.

Solutions

Solution

1class Solution {2private3  List<Integer>[] g;4private5  boolean[] vis;6private7  boolean[] has;8private9  int[] nums;10public11  int[] smallestMissingValueSubtree(int[] parents, int[] nums) {12    int n = nums.length;13    this.nums = nums;14    g = new List[n];15    vis = new boolean[n];16    has = new boolean[n + 2];17    Arrays.setAll(g, i->new ArrayList<>());18    int idx = -1;19    for (int i = 0; i < n; ++i) {20      if (i > 0) {21        g[parents[i]].add(i);22      }23      if (nums[i] == 1) {24        idx = i;25      }26    }27    int[] ans = new int[n];28    Arrays.fill(ans, 1);29    if (idx == -1) {30      return ans;31    }32    for (int i = 2; idx != -1; idx = parents[idx]) {33      dfs(idx);34      while (has[i]) {35        ++i;36      }37      ans[idx] = i;38    }39    return ans;40  }41private42  void dfs(int i) {43    if (vis[i]) {44      return;45    }46    vis[i] = true;47    if (nums[i] < has.length) {48      has[nums[i]] = true;49    }50    for (int j : g[i]) {51      dfs(j);52    }53  }54}

1class Solution {2public:3  vector<int> smallestMissingValueSubtree(vector<int> &parents,4                                          vector<int> &nums) {5    int n = nums.size();6    vector<int> g[n];7    bool vis[n];8    bool has[n + 2];9    memset(vis, false, sizeof(vis));10    memset(has, false, sizeof(has));11    int idx = -1;12    for (int i = 0; i < n; ++i) {13      if (i) {14        g[parents[i]].push_back(i);15      }16      if (nums[i] == 1) {17        idx = i;18      }19    }20    vector<int> ans(n, 1);21    if (idx == -1) {22      return ans;23    }24    function<void(int)> dfs = [&](int i) {25      if (vis[i]) {26        return;27      }28      vis[i] = true;29      if (nums[i] < n + 2) {30        has[nums[i]] = true;31      }32      for (int j : g[i]) {33        dfs(j);34      }35    };36    for (int i = 2; ~idx; idx = parents[idx]) {37      dfs(idx);38      while (has[i]) {39        ++i;40      }41      ans[idx] = i;42    }43    return ans;44  }45};

1class Solution:2    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 ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem