Merge Triplets to Form Target Triplet

1. Problem & Core Objective

You have a list of triplets and a target triplet. One operation picks two triplets i and j and replaces one of them with their element-wise maximum:

[a1, b1, c1] ⊕ [a2, b2, c2]  =  [max(a1,a2), max(b1,b2), max(c1,c2)]

Return whether some sequence of operations can produce target.

triplets = [[2,5,3],[1,8,4],[1,7,5]],  target = [2,7,5]   →  true
triplets = [[3,4,5],[4,5,6]],          target = [3,2,5]   →  false

Constraints: 1 <= triplets.length <= 10^5, 1 <= values <= 1000

What's actually being tested: whether you notice that the operation's algebra — max is idempotent, commutative, associative, and monotone — reduces a sequence-of-operations question to a subset question, and then to three independent one-dimensional questions. The code is eight lines; every one of them follows from a property of max.

2. First-Principles Thought Process

Step 1 — order and repetition don't matter

max is associative and commutative, so merging any collection of triplets gives their element-wise maximum regardless of the order. It's also idempotent, so merging the same triplet twice changes nothing.

The reachable values are exactly { elementwise-max(S) : S is a non-empty subset }.

A question about sequences of operations just became a question about subsets — from unbounded to 2^n.

Step 2 — some triplets can never be used

max only increases values. So if a triplet exceeds the target in any coordinate, including it pushes that coordinate permanently above the target, and no later operation can bring it down.

Discard every triplet with t[k] > target[k] for any k. They are unusable in any valid subset.

This is a monotonicity argument, and it's the only place the problem's difficulty lives.

Step 3 — among survivors, take everything

Every surviving triplet is <= target in all three coordinates. Adding one to the subset can only raise coordinates, and can never raise one past the target. So including more survivors is never harmful.

If any subset works, the subset of all survivors works.

2^n subsets collapsed to one.

Step 4 — three independent checks

Now the question is whether the element-wise max of all survivors equals target. Each coordinate is independent, and each coordinate is capped at target[k]. So it suffices that some survivor attains target[k] exactly:

found[k] = ∃ a surviving triplet t with t[k] == target[k]
answer   = found[0] && found[1] && found[2]

One pass, three booleans.

The chain in one line

Associativity and commutativity → subsets, not sequences. Monotonicity → filter. Monotonicity again → take all survivors. Independence of coordinates → three separate existence checks.

Every step is a property of max, not an insight about triplets. That framing is the answer to "how did you get there?"

Verified against brute force: checking all 2^n subsets agrees with the eight-line solution on all 4,000 randomized cases, including inputs deliberately biased to be satisfiable.

3. Solution Paths

Approach 1 — Brute force over all subsets

public boolean mergeTriplets(int[][] triplets, int[] target) {
    int n = triplets.length;
    for (int mask = 1; mask < (1 << n); mask++) {
        int a = 0, b = 0, c = 0;
        for (int i = 0; i < n; i++) {
            if ((mask >> i & 1) == 0) continue;
            a = Math.max(a, triplets[i][0]);
            b = Math.max(b, triplets[i][1]);
            c = Math.max(c, triplets[i][2]);
        }
        if (a == target[0] && b == target[1] && c == target[2]) return true;
    }
    return false;
}

• Time O(2^n · n) · Space O(1)

Usable only up to about n = 20; it exists to be checked against.

Counter-questions on this approach

⭐ "Why is enumerating subsets valid at all, when the problem describes a sequence of pairwise operations?"

Because max is associative and commutative, so the result depends only on which triplets were involved, not the order. And it's idempotent, so involving one twice is the same as once.

Every reachable triplet is therefore the element-wise max of some non-empty subset, and every non-empty subset is reachable by merging its members in any order. The correspondence is exact in both directions — that's what licenses the enumeration.

"Why does the mask start at 1?"

The empty subset isn't a legal outcome — there's nothing to merge, and [0,0,0] isn't a triplet you can produce. Values are at least 1, so the empty max would be wrong anyway.

"mask >> i & 1 — precedence?"

>> binds tighter than & in Java, so it parses as (mask >> i) & 1. I'd usually parenthesise it anyway; relying on remembered precedence is a bad habit in a review (22).

Approach 2 — Filter, then merge everything

public boolean mergeTriplets(int[][] triplets, int[] target) {
    int a = 0, b = 0, c = 0;
    for (int[] t : triplets) {
        if (t[0] > target[0] || t[1] > target[1] || t[2] > target[2]) continue;
        a = Math.max(a, t[0]);
        b = Math.max(b, t[1]);
        c = Math.max(c, t[2]);
    }
    return a == target[0] && b == target[1] && c == target[2];
}

• Time O(n) · Space O(1)

This is the literal transcription of §2: filter, take everything, compare.

Counter-questions on this approach

⭐ "Why is 'take all survivors' safe rather than just convenient?"

Because every survivor is coordinate-wise <= target, so adding one can only raise a coordinate toward the target, never past it. Formally: if subset S works, then max(S ∪ {t}) for any survivor t is still <= target coordinate-wise, and still >= max(S) = target. So it equals target too.

Monotone-and-capped is the general shape: when adding an element can only help and can never overshoot, greedily take all of them.

"What if no triplet survives the filter?"

Then a, b, c stay at 0, which can't equal any target since values are at least 1. Returns false correctly, with no special case.

If values could be 0 I'd need an explicit "did anything survive?" flag — worth stating, because it's the kind of constraint change that silently breaks this.

"Why is the filter a disqualification rather than a clamp?"

Because there's no operation that reduces a value. Once a coordinate exceeds the target it's permanently wrong — you can't merge your way back down. A clamp would be modelling an operation the problem doesn't offer.

Approach 3 — Three booleans (optimal, and the clearest)

public boolean mergeTriplets(int[][] triplets, int[] target) {
    boolean[] found = new boolean[3];
    for (int[] t : triplets) {
        if (t[0] > target[0] || t[1] > target[1] || t[2] > target[2]) continue;   // disqualified
        for (int i = 0; i < 3; i++)
            if (t[i] == target[i]) found[i] = true;                               // this coordinate is covered
    }
    return found[0] && found[1] && found[2];
}

• Time O(n) · Space O(1)

Counter-questions on this approach

⭐ "How is this different from Approach 2?"

It isn't, computationally — they agree on every input. But it states the decomposition explicitly: the three coordinates are independent, each is capped at target[k] by the filter, so each reduces to "does some survivor hit it exactly?"

Approach 2 reaches the same conclusion through a max that happens to be capped. Approach 3 says out loud why the cap exists.

"Can one triplet cover more than one coordinate?"

Yes — [2,7,5] against target [2,7,5] covers all three at once and the answer is immediate. Nothing requires distinct triplets for distinct coordinates, which is exactly why the three checks are independent.

That independence is the step that would fail if the operation weren't coordinate-wise.

"Does the order of the filter and the found update matter?"

Critically. The continue must come first: a disqualified triplet might still hit the target exactly in one coordinate while exceeding it in another, and letting it set found[i] would claim coverage from a triplet that can never be used.

The witness is triplets = [[2,2,5],[1,1,2]], target = [2,2,2]. The first triplet hits the target exactly in coordinates 0 and 1, but its 5 in coordinate 2 exceeds the target's 2 — so it can never be used. The second covers only coordinate 2.

With the filter: the only survivor is [1,1,2], coverage is [false, false, true], answer false — and brute force over all subsets confirms it, since [2,2,5], [1,1,2] and their merge all differ from the target. Without the filter, the disqualified triplet supplies coordinates 0 and 1 and the code returns true.

"Does this generalise past three coordinates?"

Directly — boolean[] found = new boolean[d] and two loops over d. Nothing in the argument mentions the number 3. I'd write it generically if the signature allowed it.

4. Why the Optimal Solution Wins

O(n) is a lower bound — any triplet could be the one that covers a coordinate, so all must be read.

Write Approach 3. It's the same cost as Approach 2 but it names the reasoning in the code, and found[] generalises to d dimensions without a rewrite.

5. Java Prerequisites

Iterating a jagged array

for (int[] t : triplets) { ... }      // each row is an int[]

int[][] in Java is an array of references to rows, not a rectangular block. Here every row is length 3, but the type doesn't promise that.

boolean[] defaults

boolean[] found = new boolean[3];     // all false — the correct starting state

Unlike the int[]-defaults-to-zero trap in DP problems, false genuinely is the right initial value for an existence flag.

Short-circuit || in the filter

if (t[0] > target[0] || t[1] > target[1] || t[2] > target[2]) continue;

Evaluation stops at the first true, so a triplet disqualified on its first coordinate costs one comparison.

Math.max on primitives compiles to a branchless intrinsic on modern JITs — no boxing, no call overhead.

Bitmask subset enumeration

for (int mask = 1; mask < (1 << n); mask++)
    for (int i = 0; i < n; i++)
        if ((mask >> i & 1) == 1) { /* element i is in the subset */ }

1 << n overflows for n >= 31, so this pattern silently breaks on large inputs — one more reason it's brute force only (22).

6. Interview Communication Guide

Clarifying questions: Can a triplet be used more than once (max is idempotent, so it makes no difference)? Does the result have to be stored back into the list, or is any reachable value acceptable (any reachable value)? Can values be 0 (no — minimum 1, which matters for my zero-initialisation)? Must at least one operation happen (no — a single triplet equal to the target is already an answer)?

The pitch

"I'd reason from the algebra of the operation rather than from the triplets.

max is associative and commutative, so a sequence of merges gives the same result as merging a set all at once — order is irrelevant. It's idempotent, so repeats are irrelevant too. That turns 'can some sequence of operations produce the target' into 'is the target the element-wise max of some subset'.

Next, max only increases values. So any triplet that exceeds the target in any coordinate is permanently unusable — including it pushes that coordinate too high with no way back. Filter those out.

Then the key step: among the survivors, every coordinate is already <= target, so adding more survivors can only move coordinates toward the target and never past it. Taking all of them is therefore optimal, and 2^n subsets collapse to one.

Finally the three coordinates are independent. Each is capped by the filter, so I just need each one to be hit exactly by some survivor. Three booleans, one pass.

The ordering trap is that the filter has to come before the check. A triplet can match the target exactly in one coordinate while exceeding it in another, and counting that as coverage claims a cover you can never actually use. On [[2,2,5],[1,1,2]] against target [2,2,2], the disqualified triplet is the only thing hitting coordinates 0 and 1 — checking coverage first returns true, and the answer is false.

O(n) time, O(1) space."

Edge cases to volunteer:

Name [[2,2,5],[1,1,2]] with target [2,2,2]. It's the smallest input I could construct where checking coverage before disqualification actually flips the answer — a disqualified triplet is the only thing hitting two of the three coordinates. LeetCode's own negative example, [[3,4,5],[4,5,6]] against [3,2,5], returns false either way, so it doesn't test the ordering at all.

7. Follow-Up Questions — Modified Constraints

⭐ "Return the actual subset of triplets used, not just a boolean."

Report all survivors — that's a valid answer whenever one exists, by the take-everything argument. If a minimal subset is wanted, greedily pick one survivor per uncovered coordinate: at most 3 triplets, found in one extra pass.

Minimality here is easy only because there are three coordinates. In d dimensions, finding the smallest covering subset is set cover, which is NP-hard — worth flagging, because it shows the problem's tractability is an artefact of d = 3 being tiny.

⭐ "What if the operation were element-wise min instead of max?"

Everything mirrors: disqualify triplets below the target in any coordinate, and check that each coordinate is attained exactly. The four algebraic properties hold identically for min.

The general statement: this works for any operation that is associative, commutative, idempotent and monotone — i.e. any semilattice meet or join.

"What if the operation were element-wise sum?"

Everything breaks. Sum isn't idempotent (using a triplet twice differs from once) and isn't capped, so the filter argument fails, and 'take everything' overshoots. It becomes a subset-sum question in three dimensions — NP-hard.

This is the contrast that makes the max reasoning visible: none of the four steps in §2 mentioned triplets, and all four fail for +.

"What if you could only merge adjacent triplets in the list?"

Then order matters again and the subset reduction collapses. You'd need interval DP over which contiguous ranges can be merged — the shape of Burst Balloons. The adjacency constraint is what destroys commutativity in practice.

"What if triplets had d = 10^5 coordinates?"

The algorithm is O(n · d) — still linear in the input size. found becomes a boolean[d], and the filter short-circuits on the first violated coordinate. Nothing structural changes.

"What if you wanted the number of distinct reachable triplets?"

That's counting distinct element-wise maxima over 2^n subsets — much harder, and not answered by this technique. For d = 3 with values up to 1000 you could bound it by the number of achievable coordinate triples and count with inclusion–exclusion, but there's no one-pass answer.

"Could you answer many different targets efficiently?"

Not with a single precomputation, because the filter depends on the target. For d = 3 with small values you could precompute, for each coordinate k and value v, the set of triplets attaining v in coordinate k — but the disqualification is a conjunction across coordinates, so you'd still need a per-query scan in the worst case.