Problem. Each triplet can contribute coordinates to a merged result by taking coordinate-wise maxima. Return True if some subset can form the target triplet exactly.
This is the classic coordinate-wise greedy filtering pattern.
Examples:
triplets = [[2,5,3],[1,8,4],[1,7,5]],target = [2,7,5]→Truetriplets = [[3,4,5],[4,5,6]],target = [3,2,5]→False- Any triplet with a coordinate larger than the target is unusable
Solution. A valid merge can use only triplets that never exceed the target in any coordinate. Among those safe triplets, you just need to see whether each target coordinate can be matched by at least one triplet.
def merge_triplets(triplets, target):
matched = [False, False, False]
for triplet in triplets:
if any(triplet[index] > target[index] for index in range(3)):
continue
for index in range(3):
if triplet[index] == target[index]:
matched[index] = True
return all(matched)
O(n) time, O(1) space.
Gotchas.
- Triplets that overshoot the target in any coordinate can never appear in a successful merge.
- You do not need to search subsets explicitly after filtering.
- Matching the three target coordinates can happen across different triplets.