2131. Smallest Missing Genetic Value In Each Subtree¶

Difficulty: Hard

2131. Smallest Missing Genetic Value in Each Subtree

Hard

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⁵ genetic values, each represented by an integer in the inclusive range [1, 10⁵]. 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 <= 10⁵
0 <= parents[i] <= n - 1 for i != 0
parents[0] == -1
parents represents a valid tree.
1 <= nums[i] <= 10⁵
Each nums[i] is distinct.

Solution¶

class SegmentTree {
    int n;
    int[] tree;
    SegmentTree(int sz) {
        n = 1;
        while (n < sz) {
            n <<= 1;
        }
        tree = new int[2 * n];
    }
    void set(int ind, int val) {
        ind += n;
        tree[ind] = val;
        ind >>= 1;
        while (ind > 0) {
            tree[ind] = Math.min(tree[2 * ind], tree[2 * ind + 1]);
            ind >>= 1;
        }
    }
    int get(int x) {
        int node = 1;
        while (node < n) {
            int left = (node << 1);
            int right = (node << 1) + 1;
            if (tree[left] < x) {
                node = left;
            } else {
                node = right;
            }
        }
        return (node - n);
    }
}

public class Solution {
    private ArrayList<ArrayList<Integer>> adj;
    private int first[];
    private int last[];
    private ArrayList<Integer> euler_tour;
    public int[] smallestMissingValueSubtree(int[] parents, int[] nums) {
        int n = parents.length;
        adj = new ArrayList<>();
        for (int i = 0; i <= n + 1; i++) adj.add(new ArrayList<>());
        for (int i = 1; i < n; i++) adj.get(parents[i]).add(i);
        euler_tour = new ArrayList<>();
        euler_tour.add(0);
        first = new int[n + 1];
        last = new int[n + 1];
        dfs(0, nums);
        List<int[]> queries = new ArrayList<>();
        for (int i = 0; i < n; i++) queries.add(new int[]{first[i], last[i]});
        return solve(euler_tour, queries);
    }

    private void dfs(int u, int[] nums) {
        euler_tour.add(nums[u]);
        first[u] = euler_tour.size() - 1;
        for (int v : adj.get(u)) {
            dfs(v, nums);
        }
        last[u] = euler_tour.size() - 1;
    }

    private int[] solve(List<Integer> a, List<int[]> queries) {
        int n = a.size();
        for (int i = 1; i < a.size(); i++) a.set(i, a.get(i) - 1);
        int q = queries.size();
        List<List<int[]>> queryList = new ArrayList<>();
        for (int i = 0; i <= n; i++) queryList.add(new ArrayList<>());
        for (int i = 0; i < q; i++) {
            int l = queries.get(i)[0];
            int r = queries.get(i)[1];
            queryList.get(r).add(new int[]{l, i});
        }
        List<Integer> res = new ArrayList<>(q);
        for (int i = 0; i < q; i++) res.add(0);
        SegmentTree s = new SegmentTree((int)(1e5 + 1));
        for (int i = 1; i < n; i++) {
            s.set(a.get(i), i);
            for (int[] query : queryList.get(i)) {
                int l = query[0];
                int ind = query[1];
                res.set(ind, s.get(l) + 1);
            }
        }
        int fans[] = new int[res.size()];
        for (int i = 0; i < res.size(); i++) fans[i] = res.get(i);
        return fans;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here