Can some triplets merge, by taking maxes, into a target? Skip any triplet that overshoots, then check the safe ones still reach every value.
▼The problem
LeetCode 1899 (Medium). You get a list of triplets and a target triplet. Merging two triplets takes the larger value in each position ([max(a0, b0), max(a1, b1), max(a2, b2)]); you may merge any number of times. Return whether the target can be formed exactly.
Example (LeetCode's): triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5] → true (merge the first and the last: [2,7,5]).
The solution
def mergeTriplets(triplets, target):
good = set()
for t in triplets:
if any(t[i] > target[i] for i in range(3)):
continue # poison: skip it
for i in range(3):
if t[i] == target[i]:
good.add(i)
return len(good) == 3Transcript
Merge Triplets to Form Target Triplet. You get a list of triplets, three numbers each, and one target. Merging two triplets keeps the larger number in every position. Can some merges make the target exactly?
Take two five three, one eight four, and one seven five, with the target two seven five. Merge the first and last: two, seven, five. That's the target: true.
The naive way tries every group of triplets to merge. With n triplets, that's two to the n groups. Far too many.
The greedy idea: picture each triplet as three paint levels poured into a mixer, and the target as a line on each gauge. Merging only ever raises a level, and paint never comes back out. So a triplet with any number above its line is poison: skip it. Every other triplet is safe to pour, because it can't overshoot.
In code: keep a set of good positions. Skip any triplet that goes over the target. Otherwise, mark each position where it hits the target exactly. Return whether all three are marked.
On the example: two five three is safe, and hits the first line. One eight four has eight, above seven: poison, skip it. One seven five is safe, and hits seven and five. All three lines are hit: true. But if the target were two seven six, nothing safe reaches six: false.
One pass over the triplets is order n time, and three marks are order one space.
Skip the poison, pour the rest, and check every line. That's Merge Triplets to Form Target Triplet.