Description
An operation merges two integer triplets by taking their coordinate-wise maximum and keeping that result. Decide whether some sequence of such merges can form target.
Solution
def merge_triplets(triplets, target):
matched = [False] * 3
for triplet in triplets:
if all(triplet[i] <= target[i] for i in range(3)):
for i in range(3):
matched[i] |= triplet[i] == target[i]
return all(matched)Examples
Example 1
- Input
[[[2,5,3],[1,8,4],[1,7,5]],[2,7,5]]- Output
true
Merge the first and third triplets.
Example 2
- Input
[[[3,4,5],[4,5,6]],[3,2,5]]- Output
false
Every triplet overshoots the second coordinate.
Example 3
- Input
[[[1,2,3]],[1,2,3]]- Output
true
The target already exists.
Approach
Discard any triplet with a coordinate above target because maxima can never undo that excess. Among the remaining triplets, record whether each target coordinate is matched by at least one triplet. All three matches are sufficient.
Time & space
O(n) time and O(1) auxiliary space, where n is triplet count.