Skip to content

2003. Smallest Missing Genetic Value in Each Subtree

SourceWeekly Contest 258 Q4DifficultyHardRating2415

Description

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.

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 <= 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.

Solutions

Solution 1: DFS

Thinking

With \(n \le 10^5\), scanning every subtree separately revisits nodes too often. Gene values are unique, so mex \(> 1\) can occur only on the path from the node with gene \(1\) to the root; every other node answers \(1\).

Walking that path upward only enlarges the gene set (the parent adds sibling subtrees). Already marked genes need not be rescanned.

DFS from \(\textit{idx}\) toward the root fills \(\textit{has}\); a monotone pointer \(i\) finds the smallest missing value and writes \(\textit{ans}[\textit{idx}]\).

We notice that each node has a unique gene value, so we only need to find the node \(\textit{idx}\) with gene value \(1\), and all nodes except for those on the path from node \(\textit{idx}\) to the root node \(0\) have an answer of \(1\).

Therefore, we initialize the answer array \(\textit{ans}\) to \([1,1,...,1]\), and our focus is on finding the answer for each node on the path from node \(\textit{idx}\) to the root node \(0\).

We can start from node \(\textit{idx}\) and use depth-first search to mark the gene values that appear in the subtree rooted at \(\textit{idx}\), and record them in the array \(\textit{has}\). During the search process, we use an array \(\textit{vis}\) to mark the visited nodes to prevent repeated visits.

Next, we start from \(i=2\) and keep looking for the first gene value that has not appeared, which is the answer for node \(\textit{idx}\). Here, \(i\) is strictly increasing, because the gene values are unique, so we can always find a gene value that has not appeared in \([1,..n+1]\).

Then, we update the answer for node \(\textit{idx}\), i.e., \(\textit{ans}[\textit{idx}]=i\), and update \(\textit{idx}\) to its parent node to continue the above process until \(\textit{idx}=-1\), which means we have reached the root node \(0\).

Finally, we return the answer array \(\textit{ans}\).

The time complexity is \(O(n)\), and the space complexity is \(O(n)\), where \(n\) is the number of nodes.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution:
    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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
    private List<Integer>[] g;
    private boolean[] vis;
    private boolean[] has;
    private int[] nums;

    public int[] smallestMissingValueSubtree(int[] parents, int[] nums) {
        int n = nums.length;
        this.nums = nums;
        g = new List[n];
        vis = new boolean[n];
        has = new boolean[n + 2];
        Arrays.setAll(g, i -> new ArrayList<>());
        int idx = -1;
        for (int i = 0; i < n; ++i) {
            if (i > 0) {
                g[parents[i]].add(i);
            }
            if (nums[i] == 1) {
                idx = i;
            }
        }
        int[] ans = new int[n];
        Arrays.fill(ans, 1);
        if (idx == -1) {
            return ans;
        }
        for (int i = 2; idx != -1; idx = parents[idx]) {
            dfs(idx);
            while (has[i]) {
                ++i;
            }
            ans[idx] = i;
        }
        return ans;
    }

    private void dfs(int i) {
        if (vis[i]) {
            return;
        }
        vis[i] = true;
        if (nums[i] < has.length) {
            has[nums[i]] = true;
        }
        for (int j : g[i]) {
            dfs(j);
        }
    }
}

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
func smallestMissingValueSubtree(parents []int, nums []int) []int {
    n := len(nums)
    g := make([][]int, n)
    vis := make([]bool, n)
    has := make([]bool, n+2)
    idx := -1
    ans := make([]int, n)
    for i, p := range parents {
        if i > 0 {
            g[p] = append(g[p], i)
        }
        if nums[i] == 1 {
            idx = i
        }
        ans[i] = 1
    }
    if idx < 0 {
        return ans
    }
    var dfs func(int)
    dfs = func(i int) {
        if vis[i] {
            return
        }
        vis[i] = true
        if nums[i] < len(has) {
            has[nums[i]] = true
        }
        for _, j := range g[i] {
            dfs(j)
        }
    }
    for i := 2; idx != -1; idx = parents[idx] {
        dfs(idx)
        for has[i] {
            i++
        }
        ans[idx] = i
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
function smallestMissingValueSubtree(parents: number[], nums: number[]): number[] {
    const n = nums.length;
    const g: number[][] = Array.from({ length: n }, () => []);
    const vis: boolean[] = Array(n).fill(false);
    const has: boolean[] = Array(n + 2).fill(false);
    const ans: number[] = Array(n).fill(1);
    let idx = -1;
    for (let i = 0; i < n; ++i) {
        if (i) {
            g[parents[i]].push(i);
        }
        if (nums[i] === 1) {
            idx = i;
        }
    }
    if (idx === -1) {
        return ans;
    }
    const dfs = (i: number): void => {
        if (vis[i]) {
            return;
        }
        vis[i] = true;
        if (nums[i] < has.length) {
            has[nums[i]] = true;
        }
        for (const j of g[i]) {
            dfs(j);
        }
    };
    for (let i = 2; ~idx; idx = parents[idx]) {
        dfs(idx);
        while (has[i]) {
            ++i;
        }
        ans[idx] = i;
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
impl Solution {
    pub fn smallest_missing_value_subtree(parents: Vec<i32>, nums: Vec<i32>) -> Vec<i32> {
        fn dfs(
            i: usize,
            vis: &mut Vec<bool>,
            has: &mut Vec<bool>,
            g: &Vec<Vec<usize>>,
            nums: &Vec<i32>,
        ) {
            if vis[i] {
                return;
            }
            vis[i] = true;
            if nums[i] < (has.len() as i32) {
                has[nums[i] as usize] = true;
            }
            for &j in &g[i] {
                dfs(j, vis, has, g, nums);
            }
        }

        let n = nums.len();
        let mut ans = vec![1; n];
        let mut g: Vec<Vec<usize>> = vec![vec![]; n];
        let mut idx = -1;
        for (i, &p) in parents.iter().enumerate() {
            if i > 0 {
                g[p as usize].push(i);
            }
            if nums[i] == 1 {
                idx = i as i32;
            }
        }
        if idx == -1 {
            return ans;
        }
        let mut vis = vec![false; n];
        let mut has = vec![false; (n + 2) as usize];
        let mut i = 2;
        let mut idx_mut = idx;
        while idx_mut != -1 {
            dfs(idx_mut as usize, &mut vis, &mut has, &g, &nums);
            while has[i] {
                i += 1;
            }
            ans[idx_mut as usize] = i as i32;
            idx_mut = parents[idx_mut as usize];
        }
        ans
    }
}

Solution 2: Explicit Stack

Thinking

With \(n \le 10^5\), scanning every subtree separately revisits nodes too often. Gene values are unique, so mex \(> 1\) can occur only on the path from the node with gene \(1\) to the root; every other node answers \(1\). If gene \(1\) sits at the root of a chain, recursively marking that subtree has call depth \(n\).

Walking that path upward only enlarges the gene set (the parent adds sibling subtrees). Already marked genes need not be rescanned.

An explicit stack marks the subtree from \(\textit{idx}\) toward the root and fills \(\textit{has}\). A monotone pointer \(i\) finds the smallest missing value and writes \(\textit{ans}[\textit{idx}]\).

We notice that each node has a unique gene value, so we only need to find the node \(\textit{idx}\) with gene value \(1\), and all nodes except for those on the path from node \(\textit{idx}\) to the root node \(0\) have an answer of \(1\).

Therefore, we initialize the answer array \(\textit{ans}\) to \([1,1,...,1]\), and our focus is on finding the answer for each node on the path from node \(\textit{idx}\) to the root node \(0\).

We can start from node \(\textit{idx}\) and use an explicit stack to mark the gene values that appear in the subtree rooted at \(\textit{idx}\), and record them in the array \(\textit{has}\). During the walk, we use an array \(\textit{vis}\) to mark the visited nodes to prevent repeated visits.

Next, we start from \(i=2\) and keep looking for the first gene value that has not appeared, which is the answer for node \(\textit{idx}\). Here, \(i\) is strictly increasing, because the gene values are unique, so we can always find a gene value that has not appeared in \([1,..n+1]\).

Then, we update the answer for node \(\textit{idx}\), i.e., \(\textit{ans}[\textit{idx}]=i\), and update \(\textit{idx}\) to its parent node to continue the above process until \(\textit{idx}=-1\), which means we have reached the root node \(0\).

Finally, we return the answer array \(\textit{ans}\).

The time complexity is \(O(n)\), and the space complexity is \(O(n)\), where \(n\) is the number of nodes.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution:
    def smallestMissingValueSubtree(
        self, parents: list[int], nums: list[int]
    ) -> list[int]:
        def dfs(i: int) -> None:
            stk = [i]
            while stk:
                u = stk.pop()
                if vis[u]:
                    continue
                vis[u] = True
                if nums[u] < len(has):
                    has[nums[u]] = True
                for j in g[u]:
                    stk.append(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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
    public int[] smallestMissingValueSubtree(int[] parents, int[] nums) {
        int n = nums.length;
        List<Integer>[] g = new List[n];
        Arrays.setAll(g, i -> new ArrayList<>());
        int idx = -1;
        for (int i = 0; i < n; ++i) {
            if (i > 0) {
                g[parents[i]].add(i);
            }
            if (nums[i] == 1) {
                idx = i;
            }
        }
        int[] ans = new int[n];
        Arrays.fill(ans, 1);
        if (idx == -1) {
            return ans;
        }
        boolean[] vis = new boolean[n];
        boolean[] has = new boolean[n + 2];
        for (int i = 2; idx != -1; idx = parents[idx]) {
            dfs(g, vis, has, nums, idx);
            while (has[i]) {
                ++i;
            }
            ans[idx] = i;
        }
        return ans;
    }

    private void dfs(List<Integer>[] g, boolean[] vis, boolean[] has, int[] nums, int start) {
        Deque<Integer> stk = new ArrayDeque<>();
        stk.push(start);
        while (!stk.isEmpty()) {
            int i = stk.pop();
            if (vis[i]) {
                continue;
            }
            vis[i] = true;
            if (nums[i] < has.length) {
                has[nums[i]] = true;
            }
            for (int j : g[i]) {
                stk.push(j);
            }
        }
    }
}

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
func smallestMissingValueSubtree(parents []int, nums []int) []int {
    n := len(nums)
    g := make([][]int, n)
    idx := -1
    ans := make([]int, n)
    for i, p := range parents {
        if i > 0 {
            g[p] = append(g[p], i)
        }
        if nums[i] == 1 {
            idx = i
        }
        ans[i] = 1
    }
    if idx < 0 {
        return ans
    }
    vis := make([]bool, n)
    has := make([]bool, n+2)
    dfs := func(start int) {
        stk := []int{start}
        for len(stk) > 0 {
            i := stk[len(stk)-1]
            stk = stk[:len(stk)-1]
            if vis[i] {
                continue
            }
            vis[i] = true
            if nums[i] < len(has) {
                has[nums[i]] = true
            }
            for _, j := range g[i] {
                stk = append(stk, j)
            }
        }
    }
    for i := 2; idx != -1; idx = parents[idx] {
        dfs(idx)
        for has[i] {
            i++
        }
        ans[idx] = i
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
function smallestMissingValueSubtree(parents: number[], nums: number[]): number[] {
    const n = nums.length;
    const g: number[][] = Array.from({ length: n }, () => []);
    const ans: number[] = Array(n).fill(1);
    let idx = -1;
    for (let i = 0; i < n; ++i) {
        if (i) {
            g[parents[i]].push(i);
        }
        if (nums[i] === 1) {
            idx = i;
        }
    }
    if (idx === -1) {
        return ans;
    }
    const vis: boolean[] = Array(n).fill(false);
    const has: boolean[] = Array(n + 2).fill(false);
    const dfs = (start: number): void => {
        const stk: number[] = [start];
        while (stk.length) {
            const i = stk.pop()!;
            if (vis[i]) {
                continue;
            }
            vis[i] = true;
            if (nums[i] < has.length) {
                has[nums[i]] = true;
            }
            for (const j of g[i]) {
                stk.push(j);
            }
        }
    };
    for (let i = 2; ~idx; idx = parents[idx]) {
        dfs(idx);
        while (has[i]) {
            ++i;
        }
        ans[idx] = i;
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
impl Solution {
    pub fn smallest_missing_value_subtree(parents: Vec<i32>, nums: Vec<i32>) -> Vec<i32> {
        let n = nums.len();
        let mut ans = vec![1; n];
        let mut g: Vec<Vec<usize>> = vec![vec![]; n];
        let mut idx = -1;
        for (i, &p) in parents.iter().enumerate() {
            if i > 0 {
                g[p as usize].push(i);
            }
            if nums[i] == 1 {
                idx = i as i32;
            }
        }
        if idx == -1 {
            return ans;
        }
        let mut vis = vec![false; n];
        let mut has = vec![false; n + 2];
        let mut i = 2;
        while idx != -1 {
            let mut stk = vec![idx as usize];
            while let Some(u) = stk.pop() {
                if vis[u] {
                    continue;
                }
                vis[u] = true;
                if nums[u] < has.len() as i32 {
                    has[nums[u] as usize] = true;
                }
                for &j in &g[u] {
                    stk.push(j);
                }
            }
            while has[i] {
                i += 1;
            }
            ans[idx as usize] = i as i32;
            idx = parents[idx as usize];
        }
        ans
    }
}

Comments