4.26.6 — Merge Triplets to Form Target Triplet

LeetCode 1899 · Medium

The problem

You may repeatedly pick two triplets and replace one of them with the element-wise maximum of the pair. Return true if the target triplet can be produced.

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

The pattern

Two observations turn this into a five-line problem.

Observation 1 — merging only ever increases values. The element-wise maximum can never make a component smaller. So if any triplet has a component larger than the target's, using it is fatal: that component can never come back down.

Call a triplet safe when all three of its components are ≤ the target's. Only safe triplets may be used, and every unsafe one is discarded.

Observation 2 — you may use every safe triplet. Merging two safe triplets produces another safe triplet, since the maximum of two values that are each at most the target is still at most the target. There is no downside and no choice to make: merge all of them.

So the answer is simply "after merging every safe triplet, does the result equal the target?" And because merging takes maximums, the result equals the target exactly when each component of the target is achieved by at least one safe triplet.

The solution

Python

class Solution:
    def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool:
        found = [False, False, False]        # has each target component been hit?

        for a, b, c in triplets:
            if a > target[0] or b > target[1] or c > target[2]:
                continue                     # unsafe — using it can never be undone

            if a == target[0]: found[0] = True
            if b == target[1]: found[1] = True
            if c == target[2]: found[2] = True

        return all(found)

TypeScript

function mergeTriplets(triplets: number[][], target: number[]): boolean {
  const found = [false, false, false];

  for (const [a, b, c] of triplets) {
    if (a > target[0] || b > target[1] || c > target[2]) continue;

    if (a === target[0]) found[0] = true;
    if (b === target[1]) found[1] = true;
    if (c === target[2]) found[2] = true;
  }

  return found[0] && found[1] && found[2];
}

The continue is the entire algorithm. Filtering out unsafe triplets is the greedy decision, and it is forced — there is nothing to weigh up.

A single triplet may satisfy more than one component, which is why the three checks are separate ifs rather than an elif chain.

No merging is actually performed. You never need to build the merged triplet, because "the maximum over the safe set equals the target" is the same statement as "each component is hit by some safe triplet". Recognising that saves the simulation entirely.

Trace

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

triplet	safe?	hits
[2,5,3]	yes (2≤2, 5≤7, 3≤5)	first component ✓
[1,8,4]	no — 8 > 7	discarded
[1,7,5]	yes	second and third ✓

All three found → true ✓.

The discarded triplet is the interesting one: it holds a valid 4 in the third position, but its 8 poisons it permanently.

Complexity

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

The reasoning pattern

This problem is a good illustration of a move worth naming:

When an operation is monotonic — it can only increase, or only decrease — anything that overshoots is permanently disqualified.

Filtering out the disqualified candidates is then free, and what remains can usually all be used. The same reasoning appears in:

• Bitwise OR problems — bits can only be set, never cleared, so any candidate with an extra bit is unusable.
• Prefix maximum problems — once a maximum has been raised it cannot come down.
• Monotonic stack eviction (4.8) — an element that can never win again is dropped.

Where this goes next

• Maximum Score Words, bitmask feasibility problems — the same "filter the impossible, use everything else" shape.
• Find the Maximum OR, AND of numbers in a range — monotonic bit operations with the same disqualification logic.

What the interviewer will push on

"Why can you discard a triplet with an over-large component?" Merging takes maximums, so that component can never decrease afterwards.

"Why is it safe to use every remaining triplet?" Merging two safe triplets is still safe, so there is no cost to including one.

"Why do you not simulate the merge?" The merged result equals the target exactly when each component is achieved by some safe triplet.

"Can one triplet satisfy two components?" Yes, which is why the checks are independent.

"What if the operation were element-wise minimum instead?" Mirror the argument — discard triplets with a component below the target.

One thing to volunteer: name the monotonicity. "Merging only increases values, so anything above the target is permanently unusable and everything else is free to use." Both halves of the greedy fall out of that one sentence.

Next: 4.26.7 Partition Labels — a greedy driven by one precomputed table.