{"id":8570,"date":"2021-08-11T19:55:13","date_gmt":"2021-08-12T02:55:13","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8570"},"modified":"2021-08-11T19:58:14","modified_gmt":"2021-08-12T02:58:14","slug":"leetcode-1899-merge-triplets-to-form-target-triplet","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/greedy\/leetcode-1899-merge-triplets-to-form-target-triplet\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1899. Merge Triplets to Form Target Triplet"},"content":{"rendered":"\n<p>A&nbsp;<strong>triplet<\/strong>&nbsp;is an array of three integers. You are given a 2D integer array&nbsp;<code>triplets<\/code>, where&nbsp;<code>triplets[i] = [a<sub>i<\/sub>, b<sub>i<\/sub>, c<sub>i<\/sub>]<\/code>&nbsp;describes the&nbsp;<code>i<sup>th<\/sup><\/code>&nbsp;<strong>triplet<\/strong>. You are also given an integer array&nbsp;<code>target = [x, y, z]<\/code>&nbsp;that describes the&nbsp;<strong>triplet<\/strong>&nbsp;you want to obtain.<\/p>\n\n\n\n<p>To obtain&nbsp;<code>target<\/code>, you may apply the following operation on&nbsp;<code>triplets<\/code>&nbsp;<strong>any number<\/strong>&nbsp;of times (possibly&nbsp;<strong>zero<\/strong>):<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Choose two indices (<strong>0-indexed<\/strong>)&nbsp;<code>i<\/code>&nbsp;and&nbsp;<code>j<\/code>&nbsp;(<code>i != j<\/code>) and&nbsp;<strong>update<\/strong>&nbsp;<code>triplets[j]<\/code>&nbsp;to become&nbsp;<code>[max(a<sub>i<\/sub>, a<sub>j<\/sub>), max(b<sub>i<\/sub>, b<sub>j<\/sub>), max(c<sub>i<\/sub>, c<sub>j<\/sub>)]<\/code>.<ul><li>For example, if&nbsp;<code>triplets[i] = [2, 5, 3]<\/code>&nbsp;and&nbsp;<code>triplets[j] = [1, 7, 5]<\/code>,&nbsp;<code>triplets[j]<\/code>&nbsp;will be updated to&nbsp;<code>[max(2, 1), max(5, 7), max(3, 5)] = [2, 7, 5]<\/code>.<\/li><\/ul><\/li><\/ul>\n\n\n\n<p>Return&nbsp;<code>true<\/code>&nbsp;<em>if it is possible to obtain the&nbsp;<\/em><code>target<\/code><em>&nbsp;<strong>triplet<\/strong>&nbsp;<\/em><code>[x, y, z]<\/code><em>&nbsp;as an<strong>&nbsp;element<\/strong>&nbsp;of&nbsp;<\/em><code>triplets<\/code><em>, or&nbsp;<\/em><code>false<\/code><em>&nbsp;otherwise<\/em>.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5]\n<strong>Output:<\/strong> true\n<strong>Explanation<\/strong><strong>:<\/strong> Perform the following operations:\n- Choose the first and last triplets [[2,5,3],[1,8,4],[1,7,5]]. Update the last triplet to be [max(2,1), max(5,7), max(3,5)] = [2,7,5]. triplets = [[2,5,3],[1,8,4],[2,7,5]]\nThe target triplet [2,7,5] is now an element of triplets.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> triplets = [[1,3,4],[2,5,8]], target = [2,5,8]\n<strong>Output:<\/strong> true\n<strong>Explanation:<\/strong> The target triplet [2,5,8] is already an element of triplets.\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> triplets = [[2,5,3],[2,3,4],[1,2,5],[5,2,3]], target = [5,5,5]\n<strong>Output:<\/strong> true\n<strong>Explanation: <\/strong>Perform the following operations:\n- Choose the first and third triplets [[2,5,3],[2,3,4],[1,2,5],[5,2,3]]. Update the third triplet to be [max(2,1), max(5,2), max(3,5)] = [2,5,5]. triplets = [[2,5,3],[2,3,4],[2,5,5],[5,2,3]].\n- Choose the third and fourth triplets [[2,5,3],[2,3,4],[2,5,5],[5,2,3]]. Update the fourth triplet to be [max(2,5), max(5,2), max(5,3)] = [5,5,5]. triplets = [[2,5,3],[2,3,4],[2,5,5],[5,5,5]].\nThe target triplet [5,5,5] is now an element of triplets.\n<\/pre>\n\n\n\n<p><strong>Example 4:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> triplets = [[3,4,5],[4,5,6]], target = [3,2,5]\n<strong>Output:<\/strong> false\n<strong>Explanation:<\/strong> It is impossible to have [3,2,5] as an element because there is no 2 in any of the triplets.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= triplets.length &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>triplets[i].length == target.length == 3<\/code><\/li><li><code>1 &lt;= a<sub>i<\/sub>, b<sub>i<\/sub>, c<sub>i<\/sub>, x, y, z &lt;= 1000<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Greedy<\/strong><\/h2>\n\n\n\n<p>Exclude those bad ones (whose values are greater than x, y, z), check the max value for each dimension or whether there is x, y, z for each dimension. <\/p>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  bool mergeTriplets(vector<vector<int>>& triplets, vector<int>& t) {\n    vector<int> ans(3);\n    for (const auto& c : triplets)\n      if (c[0] <= t[0] &#038;&#038; c[1] <= t[1] &#038;&#038; c[2] <= t[2])\n        for (int i = 0; i < 3; ++i)\n          ans[i] |= c[i] == t[i];\n    return ans[0] &#038;&#038; ans[1] &#038;&#038; ans[2];\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>A&nbsp;triplet&nbsp;is an array of three integers. You are given a 2D integer array&nbsp;triplets, where&nbsp;triplets[i] = [ai, bi, ci]&nbsp;describes the&nbsp;ith&nbsp;triplet. You are also given an integer&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[51],"tags":[88,31,177],"class_list":["post-8570","post","type-post","status-publish","format-standard","hentry","category-greedy","tag-greedy","tag-math","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8570","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=8570"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8570\/revisions"}],"predecessor-version":[{"id":8573,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8570\/revisions\/8573"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8570"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8570"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8570"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}