Merge Triplets to Form Target

Merge Triplets to Form Target looks intimidating because of the word "merge," but the whole problem collapses once you notice one fact: merging can only ever raise a value, never lower it. Once you see that, the answer is a single linear scan.

The slow way first

You could try every sequence of merges and see if any path reaches the target. But the number of merge orders explodes combinatorially — that search space is enormous and completely unnecessary.

The question to ask: what does a merge actually do to a single position? It takes the max of the two values there. Max never goes down. So a triplet can only ever help if all three of its values already fit under the target — otherwise it would push some position above the target, and there is no way to come back down.

The idea: keep good triplets, check the maxima

Walk the list once. A triplet is usable only if every value is <= target in its position. Throw away any triplet that overshoots anywhere. Among the usable triplets, the only thing that matters is whether, between them, they supply the target's exact value in each of the three positions. If position i of some usable triplet equals target[i], that maximum is covered. If all three positions get covered, merging the usable triplets gives exactly the target.

The key insight: a value above the target is poison, and the only thing a usable triplet can give us is an exact match at some position. We just need all three exact matches to appear somewhere.

Walk through it

Step through the animation. The target sits on top in purple. The pointer i scans each triplet. [2, 5, 3] fits everywhere and matches the target exactly at index 0 — covered. [1, 8, 4] has an 8 > 7, so it overshoots and gets discarded. [1, 7, 5] fits and matches at indices 1 and 2. The got set fills to {0, 1, 2} — all three maxima covered — so the answer is True.

Pseudocode

make an empty set called "got"        # which target positions we can hit exactly
for each triplet [a, b, c]:
    if a <= target[0] and b <= target[1] and c <= target[2]:   # usable?
        for each position i in 0, 1, 2:
            if triplet[i] == target[i]:
                add i to got           # this triplet supplies target[i]
return whether got contains all three positions {0, 1, 2}

The Python solution

def merge_triplets(triplets, target):
    got = set()
    for a, b, c in triplets:
        if a <= target[0] and b <= target[1] and c <= target[2]:
            for i in range(3):
                if (a, b, c)[i] == target[i]:
                    got.add(i)
    return len(got) == 3

• got is a set of the target positions we have managed to match exactly.
• We unpack each triplet into a, b, c and loop once over the list.
• Line 4 is the usability filter: every value must be <= target in its slot, or the triplet is poison and we skip it.
• Lines 6 to 7 record each exact match: if a usable triplet equals the target at position i, that maximum is covered.
• We return True only when all three positions {0, 1, 2} are in got.

Complexity

We do constant work per triplet (three comparisons, three equality checks) and the got set never holds more than three elements, so the extra space is O(1).

When this pattern shows up

Practice