Merge Triplets to Form Target Triplet (LeetCode 1899)

The problem

You get a list of triplets [a, b, c] and a target triplet. One operation picks two triplets and replaces one of them with their element-wise maximum. Return True if, after any number of operations, target can appear in the list.

Input:  triplets = [[2, 5, 3], [1, 8, 4], [1, 7, 5]], target = [2, 7, 5]
Output: True

Merge [2, 5, 3] and [1, 7, 5]: the max is [2, 7, 5], which is the target. [1, 8, 4] is never used.

How to think about it

Start with brute force. The result of any sequence of merges is just the element-wise max of some subset of triplets. So you could try all 2ⁿ subsets and see if any one’s max equals target. That is exponential.

First observation: max only goes up. Once a merge includes a triplet with any value above the target in some position, that position can never come back down. So any triplet with t[i] > target[i] for some i is poison: it can never be part of the answer. Throw it away.

The key insight: merging every safe triplet never hurts. A safe triplet has every value at or below the target. Merging it in can’t push any position past the target. So the best you can do is merge all safe triplets together and check whether the result equals target. That happens exactly when, for each of the three positions, some safe triplet hits the target value exactly there. Track the set of positions that have been matched; succeed if all three are covered.

Which pattern is this? Greedy filtering. The tell is a monotone operation (max, OR, union): anything that overshoots is useless, and everything else is free to include.

Approach

1. Keep a set good of positions (0, 1, 2) that some safe triplet matches exactly.
2. For each triplet t, check it is safe: t[i] <= target[i] for all three positions.
3. If it is safe, add each position i where t[i] == target[i] to good.
4. Unsafe triplets are skipped entirely.
5. Return True if good has all three positions.

Solution

def merge_triplets(triplets, target):
    good = set()                                       # positions matched exactly so far
    for t in triplets:
        if all(t[i] <= target[i] for i in range(3)):   # safe: never overshoots the target
            for i in range(3):
                if t[i] == target[i]: good.add(i)
    return len(good) == 3
# merge_triplets([[2,5,3],[1,8,4],[1,7,5]], [2,7,5]) -> True
# merge_triplets([[3,4,5],[4,5,6]], [3,2,5]) -> False

Dry run

With target = [2, 7, 5]:

All three positions are covered, so True. In the second example, [3, 4, 5] has 4 > 2 and [4, 5, 6] overshoots everywhere, so nothing is safe and the answer is False.

Complexity

• Time: O(n). Each triplet is checked in constant time.
• Space: O(1). The set holds at most three positions.

Edge cases and pitfalls

• A triplet equal to the target answers True by itself.
• No safe triplets means good stays empty: False.
• Matching a position with an unsafe triplet is the main bug. [2, 9, 0] matches position 0 of [2, 7, 5], but its 9 ruins position 1, so it must not count.
• Trying to choose a clever subset is unnecessary; including every safe triplet is always at least as good.

Related problems

• Hand of Straights (LeetCode 846): greedy where each decision is forced, so no search is needed.
• Partition Labels (LeetCode 763): another one-pass greedy over a monotone quantity (the furthest end).
• Gas Station (LeetCode 134): a feasibility check followed by a simple linear scan.