Merge Triplets to Form Target Triplet

Problem

You are given a list of triplets, where triplets[i] = [a, b, c], and a target = [x, y, z]. You may repeatedly perform this operation: pick two triplets triplets[i] and triplets[j], and replace triplets[i] with their component-wise maximum [max(ai, aj), max(bi, bj), max(ci, cj)]. (You may reuse any triplet as j as many times as you like.)

Return True if, after some sequence of operations, at least one triplet in the list becomes exactly equal to target; otherwise return False.

Examples

• triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5] → True — merge [2,5,3] with [1,7,5] to get [2,7,5].
• triplets = [[3,4,5],[4,5,6]], target = [3,2,5] → False — every triplet has a second component ≥ 4 > 2, so the y = 2 slot can never be reached.
• triplets = [[2,5,3],[2,3,4],[1,2,5],[5,2,3]], target = [5,5,5] → True — [2,5,3] supplies the 5 in slot 2, [1,2,5] supplies the 5 in slot 3, [5,2,3] supplies the 5 in slot 1; none overshoots.

Constraints

• 1 <= len(triplets) <= 10^5
• 1 <= ai, bi, ci, x, y, z <= 1000
• The 10^5 bound rules out anything exponential in the number of triplets; a single linear pass is expected.

Think about it first

TL;DR

Keep only “safe” triplets (no component exceeds the target) and check that the three target components are each hit exactly — greedy single pass, O(n) time, O(1) space.

Approach 1 — Brute force (try every subset)

A merge of a set of triplets is just their component-wise maximum, and the operation is associative and commutative, so any reachable triplet equals the component-wise max of some subset of the originals. Naively, enumerate all 2^n subsets, take each subset’s component-wise max, and check for equality with target.

from itertools import combinations
from typing import List


def mergeTriplets(triplets: List[List[int]], target: List[int]) -> bool:
    n = len(triplets)
    for r in range(1, n + 1):
        for subset in combinations(range(n), r):
            mx = [0, 0, 0]
            for i in subset:
                for k in range(3):
                    mx[k] = max(mx[k], triplets[i][k])
            if mx == target:
                return True
    return False

Complexity: O(2^n · n) time, O(n) space.

With n up to 10^5, 2^n is astronomically large — this only illustrates the meaning of “reachable”.

Approach 2 — Greedy (keep safe triplets, hit each slot)

Greedy-choice property (why the local decision is globally optimal). Because merging is component-wise max, two facts hold:

1. Unsafe triplets can never be used. If a triplet has, say, a > x, then merging it into any triplet raises that slot to at least a > x forever — max never comes back down. So the only triplets that can appear in a valid construction are the safe ones, where every component is <= target.
2. Merging all safe triplets is never worse than merging some. Adding another safe triplet to a merge can only raise components toward the target, never past it. So the single best triplet you can build is the component-wise max of all safe triplets.

Therefore the target is reachable iff that all-safe merge equals the target — which happens exactly when, across the safe triplets, some triplet already has a == x, some has b == y, and some has c == z. This turns a search over subsets into three independent existence checks, decided greedily in one pass.

from typing import List


def mergeTriplets(triplets: List[List[int]], target: List[int]) -> bool:
    x, y, z = target
    hit = [False, False, False]  # can we reach x, y, z in slots 0, 1, 2?

    for a, b, c in triplets:
        if a <= x and b <= y and c <= z:   # safe triplet only
            if a == x:
                hit[0] = True
            if b == y:
                hit[1] = True
            if c == z:
                hit[2] = True

    return all(hit)

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

All three slots hit → return True.

Complexity: O(n) time (one pass, constant work per triplet), O(1) space.

Common pitfalls

• Forgetting the safety check before crediting a hit. A triplet with a == x but b > y must not count toward slot 0 — merging it in would push y past the target. Both conditions (safe and equal) must hold.
• Simulating merges or searching subsets is unnecessary once you see that all safe triplets can be merged together without cost.
• Assuming a single triplet must supply all three target values. Different safe triplets can cover different slots; that is what merging combines.

Pattern takeaway

When an operation is monotone (here component-wise max, which never decreases), the reachable set collapses: any element that overshoots the goal is permanently disqualified, and combining all the remaining “safe” elements is both harmless and optimal. The problem reduces to checking whether the safe pieces jointly cover every part of the target — a per-coordinate existence test, not a subset search.