650. Merge Triplets to Form Target Triplet
You are given a list triplets, where triplets[i] = [a, b, c] is a triplet of positive integers, and a target triplet [x, y, z].
You may repeatedly pick any two triplets you currently have and combine them into a new one by taking the component-wise maximum: combining [a, b, c] with [d, e, f] produces [max(a, d), max(b, e), max(c, f)]. The result can be used in later combinations.
Return true if some sequence of combinations (possibly none, if a triplet already equals the target) can produce a triplet exactly equal to target, and false otherwise.
Print true or false.
Example 1:
Input: triplets = [[3,4,2],[1,5,7],[2,2,5]], target = [3,5,7]
Output: true
Explanation: Combine [3,4,2] with [1,5,7]: component-wise max gives [max(3,1), max(4,5), max(2,7)] = [3,5,7], which is exactly the target.
Example 2:
Input: triplets = [[4,2,6],[1,7,3]], target = [4,7,5]
Output: false
Explanation: The only triplet whose third value could reach 5 without overshooting is [1,7,3], but nothing supplies z = 5: [4,2,6] has 6 > 5, so using it would overshoot the last component forever. The target is unreachable.
Constraints:
- 1 ≤ triplets.length ≤ 10⁵
- 1 ≤ a, b, c, x, y, z ≤ 1000
Hints:
Taking a maximum can only push values up, never down. What does that say about a triplet with any component larger than the target's?
Any triplet that exceeds the target in some coordinate can never be used — one merge with it poisons that coordinate permanently. Discard those and look at what's left.
Among the surviving triplets every component is <= the target's, so merging them all can never overshoot. You only need each target component to be hit exactly by at least one survivor: track three booleans.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: triplets = [[3,4,2],[1,5,7],[2,2,5]], target = [3,5,7]
Expected output: true