{"id":8743,"date":"2021-11-20T23:38:06","date_gmt":"2021-11-21T07:38:06","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8743"},"modified":"2021-11-20T23:39:00","modified_gmt":"2021-11-21T07:39:00","slug":"leetcode-2003-smallest-missing-genetic-value-in-each-subtree","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-2003-smallest-missing-genetic-value-in-each-subtree\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2003. Smallest Missing Genetic Value in Each Subtree"},"content":{"rendered":"\n

There is a family tree<\/strong> rooted at 0<\/code> consisting of n<\/code> nodes numbered 0<\/code> to n - 1<\/code>. You are given a 0-indexed<\/strong> integer array parents<\/code>, where parents[i]<\/code> is the parent for node i<\/code>. Since node 0<\/code> is the root<\/strong>, parents[0] == -1<\/code>.<\/p>\n\n\n\n

There are 105<\/sup><\/code> genetic values, each represented by an integer in the inclusive<\/strong> range [1, 105<\/sup>]<\/code>. You are given a 0-indexed<\/strong> integer array nums<\/code>, where nums[i]<\/code> is a distinct <\/strong>genetic value for node i<\/code>.<\/p>\n\n\n\n

Return an array <\/em>ans<\/code> of length <\/em>n<\/code> where <\/em>ans[i]<\/code> is<\/em> the smallest<\/strong> genetic value that is missing<\/strong> from the subtree rooted at node<\/em> i<\/code>.<\/p>\n\n\n\n

The subtree<\/strong> rooted at a node x<\/code> contains node x<\/code> and all of its descendant<\/strong> nodes.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> parents = [-1,0,0,2], nums = [1,2,3,4]\nOutput:<\/strong> [5,1,1,1]\nExplanation:<\/strong> The answer for each subtree is calculated as follows:\n- 0: The subtree contains nodes [0,1,2,3] with values [1,2,3,4]. 5 is the smallest missing value.\n- 1: The subtree contains only node 1 with value 2. 1 is the smallest missing value.\n- 2: The subtree contains nodes [2,3] with values [3,4]. 1 is the smallest missing value.\n- 3: The subtree contains only node 3 with value 4. 1 is the smallest missing value.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> parents = [-1,0,1,0,3,3], nums = [5,4,6,2,1,3]\nOutput:<\/strong> [7,1,1,4,2,1]\nExplanation:<\/strong> The answer for each subtree is calculated as follows:\n- 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.\n- 1: The subtree contains nodes [1,2] with values [4,6]. 1 is the smallest missing value.\n- 2: The subtree contains only node 2 with value 6. 1 is the smallest missing value.\n- 3: The subtree contains nodes [3,4,5] with values [2,1,3]. 4 is the smallest missing value.\n- 4: The subtree contains only node 4 with value 1. 2 is the smallest missing value.\n- 5: The subtree contains only node 5 with value 3. 1 is the smallest missing value.\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> parents = [-1,2,3,0,2,4,1], nums = [2,3,4,5,6,7,8]\nOutput:<\/strong> [1,1,1,1,1,1,1]\nExplanation:<\/strong> The value 1 is missing from all the subtrees.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • n == parents.length == nums.length<\/code><\/li>
  • 2 <= n <= 105<\/sup><\/code><\/li>
  • 0 <= parents[i] <= n - 1<\/code> for i != 0<\/code><\/li>
  • parents[0] == -1<\/code><\/li>
  • parents<\/code> represents a valid tree.<\/li>
  • 1 <= nums[i] <= 105<\/sup><\/code><\/li>
  • Each nums[i]<\/code> is distinct.<\/li><\/ul>\n\n\n\n
    Solution: DFS on a single path<\/strong><\/h2>\n\n\n\n
    One ancestors of node with value of 1 will have missing values greater than 1. We do a dfs on the path that from node with value 1 to the root.<\/p>\n\n\n\n
    Time complexity: O(n + max(nums))
    Space complexity: O(n + max(nums)) <\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector smallestMissingValueSubtree(vector& parents, vector& nums) {\n    const int n = parents.size();\n    vector ans(n, 1);\n    vector seen(100002);\n    vector> g(n);\n    for (int i = 1; i < n; ++i)\n      g[parents[i]].push_back(i);\n    function dfs = [&](int u) {\n      if (seen[nums[u]]++) return;\n      for (int v : g[u]) dfs(v);\n    };\n    int u = find(begin(nums), end(nums), 1) - begin(nums);\n    for (int l = 1; u < n && u != -1; u = parents[u]) {\n      dfs(u);\n      while (seen[l]) ++l;\n      ans[u] = l;\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[45],"tags":[33,217,28],"class_list":["post-8743","post","type-post","status-publish","format-standard","hentry","category-tree","tag-dfs","tag-hard","tag-tree","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8743","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8743"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8743\/revisions"}],"predecessor-version":[{"id":8745,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8743\/revisions\/8745"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8743"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8743"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8743"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}