Greedy crash course ↗ · 85

1899. Merge Triplets to Form Target Triplet

The merge operation is just component-wise max, so any triplet that overshoots one target component can never be used safely. Ignore those triplets and ask: can the remaining ones collectively reach every target component? One linear scan decides it.

● MediumGreedyArrayTypeScript

PROBLEM What we're solving

You have a list of triplets [a, b, c] and a target = [x, y, z]. The only allowed operation is to pick two triplets and replace one of them with the component-wise max: [max(a1,a2), max(b1,b2), max(c1,c2)]. You can do this any number of times. Return true if you can reach target, otherwise false.

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

  • [1,8,4]has component 2 = 8 > target[1] = 7 → skip.
  • Merge [2,5,3] and [1,7,5]: [max(2,1), max(5,7), max(3,5)] = [2,7,5] ✓

Output: true.

KEY IDEA Only safe triplets can contribute

Insight → merging is component-wise max, so it can only ever raise a component. If any component of a triplet exceeds the corresponding target component, merging it in would permanently overshoot that slot — no future operation can lower it. Therefore, discard every triplet with any component above target. Among the remaining "safe" triplets, take the running component-wise max. If that max equals the target, return true.

RECIPE Filter, accumulate, compare

  • 0 · Unpack target. Let [ta, tb, tc] = target. These are the exact values we need in each slot.
  • 1 · Filter unsafe triplets. For each triplet [x, y, z], skip it if x > ta || y > tb || z > tc. A single over-limit component would permanently ruin that slot if merged.
  • 2 · Accumulate component-wise max. For every safe triplet, update a running best: a = max(a, x), b = max(b, y), c = max(c, z). This simulates merging all safe triplets into one.
  • 3 · Check equality. Return a === ta && b === tb && c === tc. If any slot falls short, no combination of safe triplets can fill it.
Classic confusion → students often worry about order— which pairs to merge first. Order doesn't matter! Since merge is component-wise max, you can merge all safe triplets simultaneously (or in any sequence) and get the same result. The running-max accumulator captures this exactly.

COST Complexity & alternatives

Try all subsets
O(2ⁿ)
Check every subset of triplets exhaustively.
Greedy filter + max
O(n)
One pass; O(1) extra space (3 accumulators).

The greedy insight eliminates the need for any search. Because merge is monotone (values only go up), there is never a reason to use a triplet that exceeds the target — and using every safe triplet is always at least as good as using a subset.

Pattern transfer → this "filter then accumulate" pattern recurs in Maximum OR of Array (skip elements that push a bit too high), Largest Number After Digit Swaps by Parity (safe swaps only), and problems where a merge/combine operation is monotone— once you overshoot, you can't undo it, so simply never pick those candidates.

RUN IT Filter unsafe triplets, accumulate component-wise max

step 0 / 6
STARTScan triplets against [2,7,5]. Skip any triplet where a component exceeds the target; accumulate component-wise max over the rest.
1function mergeTriplets(triplets: number[][], target: number[]): boolean {
2▶  const [ta, tb, tc] = target;
3▶  let a = 0, b = 0, c = 0;
4 
5  for (const [x, y, z] of triplets) {
6    // Skip any triplet that could "pollute" a target component.
7    if (x > ta || y > tb || z > tc) continue;
8 
9    // Safe triplet: take the component-wise max.
10    a = Math.max(a, x);
11    b = Math.max(b, y);
12    c = Math.max(c, z);
13  }
14 
15  return a === ta && b === tb && c === tc;
16}
triplets[2,5,3]0[1,8,4]1[1,7,5]2
State
—
i
—
triplet
—
eligible
[]
good
0
acc[0]
0
acc[1]
0
acc[2]
[2,7,5]
target
current tripletskipped (unsafe)accumulator updatedmatches target
slowfast

TYPESCRIPT The solution, annotated

mergeTriplets.ts
function mergeTriplets(triplets: number[][], target: number[]): boolean {
  const [ta, tb, tc] = target;
  let a = 0, b = 0, c = 0;

  for (const [x, y, z] of triplets) {
    // Skip any triplet that could "pollute" a target component.
    if (x > ta || y > tb || z > tc) continue;

    // Safe triplet: take the component-wise max.
    a = Math.max(a, x);
    b = Math.max(b, y);
    c = Math.max(c, z);
  }

  return a === ta && b === tb && c === tc;
}

Reading it block by block

Line 2 — unpack target. Destructure into ta, tb, tc for clean comparisons. Initialize accumulators a, b, c to 0 — the identity for max.
Lines 5–6 — safety filter. Skip any triplet where at least one component exceeds the corresponding target. Merging such a triplet would permanently raise an accumulator above the target with no way to lower it.
Lines 9–11 — running max. For each safe triplet, update the three accumulators with Math.max. After the loop, [a, b, c] equals what you would get by merging every safe triplet together (order irrelevant because max is commutative and associative).
Line 14 — exact equality check. If all three accumulators exactly match the target components, the target is reachable. If any slot is still below target, no combination of safe triplets can fill it.
Complexity → O(n) time — one pass over the array, constant work per triplet. O(1) space — only three accumulator variables regardless of input size.

INTERVIEWFollow-ups they'll ask

  • "What if triplets can have more than 3 components?" Generalize: iterate over components, skip if any component exceeds target[i], then take running max. Same O(n · k) time where k is the tuple length.
  • "Return the indices of triplets used?"Track which safe triplets actually contributed a component equal to the target (i.e., the triplet that "donated" each slot). You need one index per slot, or report all contributing triplets.
  • "What if the merge operation were min instead of max?"Then merging can only lower components. You'd filter out triplets that are below any target component, and check that the running min equals target.
  • "Edge case: target already in the array?" That triplet is trivially safe (no component exceeds target), so the loop finds it and the accumulators reach target exactly. The algorithm handles this without a special case.
  • "Why can't we greedily pick the triplet closest to target?" Because you might need components from different triplets. The correct approach uses all safe triplets (their combined max), not the single best one.

MNEMONIC The one-liner

"Any component above target poisons the merge — filter it out, then max the survivors."

TRIGGERS When you see ___ → reach for ___

component-wise max / merge of tuplesgreedy filter + running max
operation only increases valuesskip if any component exceeds target
"can we reach target by combining?"accumulate max over safe candidates
merge order doesn't mattermax is commutative — one pass suffices

SKELETON The reusable shape

skeleton.ts
function mergeTriplets(triplets: number[][], target: number[]): boolean {
  const [ta, tb, tc] = target;
  let a = 0, b = 0, c = 0;

  for (const [x, y, z] of triplets) {
    if (x > ta || y > tb || z > tc) continue;
    a = Math.max(a, x);
    b = Math.max(b, y);
    c = Math.max(c, z);
  }

  return a === ta && b === tb && c === tc;
}

FLASHCARDS Tap to flip

Why skip a triplet that exceeds any target component?
Merge only raises values — an overshoot can never be corrected by further merges.
tap to flip
1 / 7
Answer to reveal explanations. No penalty for retries.Score: 0 / 9
QUESTION 01
triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5]. Which triplet is filtered out?
QUESTION 02
Why is it always safe to skip a triplet that exceeds any target component?
QUESTION 03
What is the time complexity of the greedy solution?
QUESTION 04
After processing all safe triplets for triplets = [[2,5,3],[1,7,5]], target = [2,7,5], the accumulators are:
QUESTION 05
triplets = [[3,4,5],[4,5,6]], target = [3,2,5]. Result?
QUESTION 06
The merge operation is commutative and associative. What does this imply for the algorithm?
QUESTION 07
Suppose target = [2,7,5] and the only safe triplet after filtering is [2,5,3]. What does the algorithm return?
QUESTION 08
#1899 · Merge Triplets to Form Target TripletFilter out triplets with any component exceeding the corresponding target component (they could corrupt a valid merge). Among the remaining, check that each component of the target is achievable by at least one triplet.Which algorithmic approach does this primarily use?
QUESTION 09
#1899 · Merge Triplets to Form Target TripletFilter out triplets with any component exceeding the corresponding target component (they could corrupt a valid merge). Among the remaining, check that each component of the target is achievable by at least one triplet.Which implementation correctly solves it?