Merge Triplets to Form Target Triplet

A first instinct is: take the element-wise maximum across all triplets and check whether it equals target.

class Solution:
    def mergeTriplets(self, triplets: list[list[int]], target: list[int]) -> bool:
        best = [0, 0, 0]
        for t in triplets:
            best[0] = max(best[0], t[0])
            best[1] = max(best[1], t[1])
            best[2] = max(best[2], t[2])
        return best == target

This is wrong. Merging is a real choice — you never have to merge in a triplet that would push a coordinate past what you need. But this code force-includes every triplet’s every coordinate, including ones that overshoot target. For example, with triplets = [[2,5,3],[3,999,4],[1,7,5]] and target = [2,7,5], the answer should be true (ignore the middle triplet, merge the first and last), but this naive max gives [3,999,5], which is not target — a false negative. Runs in O(n) time but produces the wrong answer.

The fix is one filtering step: a triplet is only ever safe to merge in if none of its coordinates exceeds the corresponding coordinate of target — since merges only take maximums, any coordinate already too large can never be brought back down, so including such a triplet can only hurt, never help. Discard every triplet with any coordinate > target, then take the element-wise max of what remains and compare to target.

class Solution:
    def mergeTriplets(self, triplets: list[list[int]], target: list[int]) -> bool:
        best = [0, 0, 0]
        for t in triplets:
            if t[0] <= target[0] and t[1] <= target[1] and t[2] <= target[2]:
                best[0] = max(best[0], t[0])
                best[1] = max(best[1], t[1])
                best[2] = max(best[2], t[2])
        return best == target

Watch the filter decide each row before any merging happens, and the running best vector grow toward the target.

Tracing triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5]:

• [2,5,3]: 2<=2, 5<=7, 3<=5 — safe. best = [2,5,3].
• [1,8,4]: 8 > 7 — discard (it can never help; using it would inject an 8 into the middle coordinate that could never be reduced back to 7).
• [1,7,5]: 1<=2, 7<=7, 5<=5 — safe. best = [max(2,1), max(5,7), max(3,5)] = [2,7,5].

best == target → true, matching the expected merge of triplets 0 and 2.

Why it’s correct: merging is monotone — every coordinate can only grow, never shrink. So a triplet with any coordinate exceeding target is permanently disqualified from ever contributing to reaching target exactly; it isn’t just unhelpful, it is actively poisonous if used. Among the triplets that are safe (no coordinate exceeds target), taking the coordinate-wise max of all of them is exactly what repeated merging can achieve, and it is the best possible result — if even that maximum falls short of target in some coordinate, no sequence of merges can reach it, because no available triplet supplies that value there. Complexity: one pass, three running values → O(n) time, O(1) space.