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.

Restating the Problem: You are given an array of 3-element arrays (triplets) and a target 3-element array. You can combine any two triplets by taking the maximum of each corresponding element to form a new triplet. Can you combine some subset of the given triplets to exactly form the target?

• Constraints to note: The number of triplets can be up to 10^5.
• Edge cases: The target might already be present in the input array. No merges are needed, our logic should naturally handle this.

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

Brute Force Approach

A naive approach might try generating all possible triplets by merging every combination of subsets of the input. Since each triplet can either be included or excluded, there are 2^n possible subsets. For N=10^5, 2^{100000} is astronomically large, making any brute force search impossible. We need a property that lets us make a single pass.

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.

Code Walkthrough:

• Initialization: We create a boolean array found of size 3, all initially False, to track if we've seen the target value for each of the three positions among our "safe" triplets.
• Filtering (The Greedy Choice): We loop over every triplet [a, b, c]. If any element a, b, or c is strictly greater than the corresponding target element target[0], target[1], or target[2], this triplet is poisonous. We continue and ignore it.
• Recording Hits: If the triplet is safe, we check if a exactly matches target[0]. If so, we've found our required value for the first position, so we set found[0] = True. We do the same for b and c.
• Return: Finally, we return True if all three elements of found are True, meaning we hit every required target value using only safe triplets.

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.

• Time Complexity: O(n). We iterate through the list of n triplets exactly once. For each triplet, we do a constant number of comparisons.
• Space Complexity: O(1). We only use an array found of size 3, which takes constant space regardless of n.

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.