LeetCode 2003: Smallest Missing Genetic Value in Each Subtree Solution

Master LeetCode problem 2003 (Smallest Missing Genetic Value in Each Subtree), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2003. Smallest Missing Genetic Value in Each Subtree

Hard

Dynamic Programming Tree Depth-First Search Union Find

Problem Explanation

Explanation:

To solve this problem, we can use a Depth First Search (DFS) traversal of the tree starting from the root node. For each node, we keep track of the genetic values present in its subtree. We also maintain a set to store the missing genetic values in the subtree rooted at the current node.

Start the DFS traversal from the root node (node 0).
At each node, keep track of the genetic values present in its subtree using a set.
Initialize a set to store the missing genetic values in the subtree.
Traverse the children of the current node recursively.
For each child, update the set of genetic values present in the subtree.
After traversing all children, find the smallest missing genetic value not present in the subtree.
Repeat this process for all nodes in the tree to get the answer array.

Time Complexity: O(n), where n is the number of nodes in the tree. Space Complexity: O(n) for the recursive stack and set to store genetic values.

Solution Code

class Solution {
    public int[] smallestMissingValueSubtree(int[] parents, int[] nums) {
        int n = parents.length;
        List<Integer>[] tree = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            tree[i] = new ArrayList<>();
        }
        for (int i = 1; i < n; i++) {
            tree[parents[i]].add(i);
        }
        int[] ans = new int[n];
        Arrays.fill(ans, 1);
        boolean[] seen = new boolean[105];
        int[] dp = new int[105];
        int missing = 1;
        for (int i = 0; i < n; i++) {
            dfs(i, tree, nums, ans, seen, dp, missing);
            missing = Math.max(missing, dp[nums[i]]);
        }
        return ans;
    }

    private void dfs(int node, List<Integer>[] tree, int[] nums, int[] ans, boolean[] seen, int[] dp, int missing) {
        if (seen[nums[node]]) {
            dp[nums[node]]++;
        } else {
            seen[nums[node]] = true;
        }
        for (int child : tree[node]) {
            dfs(child, tree, nums, ans, seen, dp, missing);
        }
        if (seen[nums[node]]) {
            dp[nums[node]]--;
        } else {
            ans[node] = missing;
        }
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2003 (Smallest Missing Genetic Value in Each Subtree)?

This page provides optimized solutions for LeetCode problem 2003 (Smallest Missing Genetic Value in Each Subtree) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2003 (Smallest Missing Genetic Value in Each Subtree)?

The time complexity for LeetCode 2003 (Smallest Missing Genetic Value in Each Subtree) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2003 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2003 in Java, C++, or Python.

Back to LeetCode Solutions