[LeetCode]Smallest Missing Genetic Value in Each Subtree

Problem: 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^5 genetic values, each represented by an integer in the inclusive range [1, 10^5]. 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:

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.

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.

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.

Approach: If the tree is given then we can use Post Order traversal but here making a tree can take O(n^2) so let's try to do better.

First thing which we can immediately notice is we just need to care about the path in the tree which contains 1. Otherwise for other nodes it's just 1, right. Now it's easy for us, we will find the index in nums with value 1 and then we can do dfs on it. Then we go to it's parent, do dfs on it and loop on it. We can use visited kind of set not to redo DFS on which we have already done it.

That's all!

Implementation in C#:

    public int[] SmallestMissingValueSubtree(int[] parents, int[] nums)

    {

        int length = parents.Length;

        Dictionary<int, List<int>> tree = new Dictionary<int, List<int>>();

        for (int i = 0; i < parents.Length; ++i)

        {

            if (!tree.ContainsKey(parents[i]))

            {

                tree[parents[i]] = new List<int>();

            }

            tree[parents[i]].Add(i);

        }

        int[] result = Enumerable.Repeat(1, length).ToArray();

        int index = Array.IndexOf(nums, 1);

        int currMissingNum = 1;

        HashSet<int> subTreeElems = new HashSet<int>();

        while (index != -1)

        {

            this.SmallestMissingValueSubtreeDFS(

                                        tree,

                                        nums,

                                        index,

                                        subTreeElems);

           

            while (subTreeElems.Contains(currMissingNum))

            {

                ++currMissingNum;

            }

            result[index] = currMissingNum;

            index = parents[index];

        }

        return result;

    }

    private void SmallestMissingValueSubtreeDFS(

                            Dictionary<int, List<int>> tree,

                            int[] nums,

                            int index,

                            HashSet<int> subTreeElems)

    {

        if (subTreeElems.Contains(nums[index]))

        {

            return;

        }

        subTreeElems.Add(nums[index]);

        if (tree.ContainsKey(index))

        {

            foreach (int child in tree[index])

            {

                this.SmallestMissingValueSubtreeDFS(tree, nums, child, subTreeElems);

            }

        }

    }

Complexity: O(n)