2003. Smallest Missing Genetic Value in Each Subtree LeetCode Solution
In this guide, you will get 2003. Smallest Missing Genetic Value in Each Subtree LeetCode Solution with the best time and space complexity. The solution to Smallest Missing Genetic Value in Each Subtree problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Smallest Missing Genetic Value in Each Subtree
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 105 genetic values, each represented by an integer in the inclusive range [1, 105]. 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.
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 <= 105
0 <= parents[i] <= n – 1 for i != 0
parents[0] == -1
parents represents a valid tree.
1 <= nums[i] <= 105
Each nums[i] is distinct.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
2003. Smallest Missing Genetic Value in Each Subtree LeetCode Solution in C++
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);
}
}; /* code provided by PROGIEZ */
2003. Smallest Missing Genetic Value in Each Subtree LeetCode Solution in Java
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;
}
} // code provided by PROGIEZ
2003. Smallest Missing Genetic Value in Each Subtree LeetCode Solution in Python
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 # code by PROGIEZ
