We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Smallest Missing Genetic Value in Each Subtree

Difficulty: Hard

Problem Description

Given a family tree rooted at node 0, represented by a parents array, and an array of distinct genetic values for each node, return an array where each element represents the smallest genetic value that is missing from the subtree rooted at that node.

Key Insights

  • Each node in the tree can have multiple descendants, and we need to evaluate the genetic values for each subtree.
  • The genetic values are distinct integers within a defined range, allowing for efficient tracking of missing values.
  • Depth-First Search (DFS) can be employed to traverse the tree and collect genetic values in each subtree.
  • A boolean array can be used to track which genetic values are present in a subtree, enabling quick determination of the smallest missing value.

Space and Time Complexity

Time Complexity: O(n) - Each node and its associated values are processed once. Space Complexity: O(n) - Storage for the boolean array and the result array.

Solution

To solve the problem, we can use a Depth-First Search (DFS) approach:

  1. Build an adjacency list to represent the tree structure from the parents array.
  2. Initialize a result array to store the smallest missing value for each node.
  3. For each node, perform a DFS to collect genetic values from its subtree:
    • Use a boolean array to track which genetic values are present in the subtree.
    • After collecting the values, determine the smallest missing value by checking the boolean array.
  4. Store the result for each node and return the final results.

The algorithm efficiently traverses the tree and utilizes a boolean array to manage the presence of genetic values, allowing for quick retrieval of the smallest missing genetic value.

Code Solutions

def smallestMissingValueInEachSubtree(parents, nums):
    n = len(parents)
    tree = [[] for _ in range(n)]
    for i in range(1, n):
        tree[parents[i]].append(i)

    # Map genetic values to their corresponding nodes
    genetic_map = {}
    for i in range(n):
        genetic_map[i] = nums[i]

    # Result array to store the smallest missing value for each node
    result = [0] * n

    def dfs(node):
        present = [False] * (n + 1)  # To track present genetic values
        present[genetic_map[node]] = True

        for child in tree[node]:
            child_present = dfs(child)
            for value in child_present:
                present[value] = True

        # Find the smallest missing value
        for missing in range(1, n + 2):
            if not present[missing]:
                result[node] = missing
                break

        return present

    dfs(0)
    return result
← Back to All Questions