Merge Triplets to Form Target Triplet

GREEDY · MEDIUM

The problem

A triplet is just an array of 3 integers, [a, b, c]. You’re given a list of triplets and a target triplet. The only operation you’re allowed is: pick any two triplets i and j, and overwrite triplets[j] with the coordinate-wise maximum of the two — [max(a_i, a_j), max(b_i, b_j), max(c_i, c_j)]. You can do this any number of times, on any pair, in any order. Return true if some sequence of these merges can turn one of the triplets into exactly target.

The trap is that this reads like a search problem — “try combinations of merges until one works” — when it’s actually a single-pass filtering problem in disguise.

Solution 1: Brute force — actually simulate the merges

Take the operation literally: merge every pair of currently-known triplets, keep any result that’s new, and repeat until a full round produces nothing new (a fixed point) or target shows up. This is honest and correct — it explores every triplet reachable by some sequence of merges — but it does real work for something that turns out not to need any merging at all.

Interactive visualization

pair being merged this stepnewly discovered tripletmatches targettarget (reference row)

Solution 1: Brute force — actually simulate the merges

triplets = [[2,5,3], [1,8,4], [1,7,5]], target = [2,7,5] — merge every pair, repeat until fixed point or target found

Press Play or Step to begin.

Step 0 / 0

Solution 2: Optimal — greedy check, no merging needed

checking this tripletdiscarded — overshoots targetusable — kepttarget coordinate achievedtarget coordinate not yet achieved

triplets = [[2,5,3], [1,8,4], [1,7,5]], target = [2,7,5] — filter usable triplets, track achieved coordinates

Press Play or Step to begin.

Step 0 / 0

The code

function mergeTripletsBruteForce(triplets, target) {
  let known = triplets.map((t) => t.slice());

  const has = (t) => known.some((k) => k[0] === t[0] && k[1] === t[1] && k[2] === t[2]);
  if (has(target)) return true;

  let progress = true;
  while (progress) {
    progress = false;
    const n = known.length;
    for (let i = 0; i < n; i++) {
      for (let j = i + 1; j < n; j++) {
        const merged = [
          Math.max(known[i][0], known[j][0]),
          Math.max(known[i][1], known[j][1]),
          Math.max(known[i][2], known[j][2]),
        ];
        if (!has(merged)) {
          known.push(merged);
          progress = true;
          if (has(target)) return true;
        }
      }
    }
  }
  return has(target);
}

Line by line:

known starts as a copy of the input and only ever grows — a triplet, once discovered as reachable, is never thrown away, since the real operation lets you choose freely which pair to merge next.
i < j (not all ordered pairs) is enough — merging i into j and j into i produce the same coordinate-wise max, so trying both directions would be redundant work.
const n = known.length is captured once per round, so triplets discovered mid-round get merged against each other on the next round, not this one — that’s what makes “round” a meaningful, countable unit of work.
progress tracks whether a round added anything; when a full round adds nothing new, the known set has stabilized and no further merge can ever produce target.

Complexity

Time	Space	Approach
O(n²) per round × rounds until fixed point	O(n³) worst case (growing known set)	Literal merge simulation, BFS over reachable triplets

The known set’s growth is bounded by O(n³), not O(n²): a merged triplet’s 3 coordinates are each drawn independently from up to n distinct a-values, b-values, and c-values seen across the input, so the reachable set can grow past n² before it stabilizes — it’s bounded by the product of distinct values per coordinate, not by the number of merge pairs.

Solution 2: Optimal — greedy check, no merging needed

The key insight: merging only ever takes a coordinate-wise maximum, so merging never makes any coordinate smaller. That means a triplet that already has a coordinate exceeding target can never be merged into anything useful — including it in any merge chain would carry that overshoot forward forever. So the only triplets worth looking at are the “usable” ones: a ≤ x && b ≤ y && c ≤ z. Among those, just track which of target’s 3 coordinates get hit exactly by some usable triplet. If all 3 get hit, merging all the triplets that hit them (in one shot) produces exactly target — no actual merge operation needs to be simulated to know that.

The code

function mergeTripletsOptimal(triplets, target) {
  const [x, y, z] = target;
  const achieved = new Set();

  for (const [a, b, c] of triplets) {
    if (a <= x && b <= y && c <= z) {
      if (a === x) achieved.add('x');
      if (b === y) achieved.add('y');
      if (c === z) achieved.add('z');
    }
  }

  return achieved.size === 3;
}

Line by line:

a <= x && b <= y && c <= z is the usability gate — all three coordinates must fit, since a triplet is atomic: you can’t merge in just its good coordinates and leave the bad one behind.
The three if checks after the gate use strict equality (===, not <=) — a coordinate is only “achieved” once some usable triplet hits it exactly, since max of several values below target would still be below target, never equal to it.
achieved is a Set of at most 3 possible members ('x', 'y', 'z') — it doesn’t matter which triplets contribute which coordinate, or in what order they’re checked, only that all 3 end up covered by some usable triplet.
achieved.size === 3 is the only thing that matters at the end — no merge is ever actually performed, because merging all the contributing usable triplets together is guaranteed to reproduce target exactly.

Complexity

Time	Space	Approach
O(n)	O(1)	Single linear pass, greedy filter + achieved-coordinate tracking

Complexity comparison

Solution	Time	Space
Brute force (simulate real merges)	O(n²) per round × rounds until fixed point	O(n³) worst case
Optimal (greedy filter + achieved set)	O(n)	O(1)

Interview corner

Why doesn’t the optimal solution need to perform any actual merge operation?

The only operation available is coordinate-wise max, which never decreases a value.
A triplet that already overshoots target on some coordinate stays overshooting forever — merging it into anything only carries that overshoot along.
So a triplet’s own coordinates, unmerged, already tell you everything you need: is it safe to use, and which target coordinates does it already hit exactly.

Why must all 3 coordinates of a triplet fit under target, instead of checking each coordinate independently across different triplets?

A triplet is atomic — merging it in applies max to all 3 of its coordinates simultaneously, you can’t take only the “good” ones.
Example: [2, 9, 3] against target [5, 7, 5] — its a and c look fine, but b = 9 > 7 poisons the whole triplet for use, no matter how good the other two coordinates are.
That’s exactly why the code checks all three conditions together before it ever looks at individual coordinate matches.

Could two different usable triplets that each achieve different coordinates actually be merged together to reach target, or is that just assumed?

It’s guaranteed, not assumed — every usable triplet has all 3 coordinates ≤ the corresponding target coordinate.
Merging any set of usable triplets takes the coordinate-wise max across all of them, which can never exceed target on any coordinate (since none of the inputs do).
If every target coordinate is hit exactly by at least one triplet in that set, the max on that coordinate is exactly target’s value — so the merged result equals target on all 3 coordinates simultaneously.

↳ Common follow-up: “Do you need to know which specific triplets to merge?” No — for a yes/no reachability answer, only the count of achieved coordinates matters. (To actually construct the merge sequence, you’d separately track one contributing triplet per coordinate.)

Trick question — what does this log?

const triplets = [[2, 5, 3], [1, 8, 4]];
const target = [2, 5, 3];
console.log(triplets.includes(target));

Answer: false — even though [2, 5, 3] is right there as triplets[0].
Array.prototype.includes compares with ===, and two different array literals with identical contents are never === equal — they’re different objects in memory.
triplets.includes(target) would only return true if target were the exact same array reference already inside triplets.

⚠ Trap: this is exactly why both solutions above compare triplets coordinate-by-coordinate (k[0] === t[0] && k[1] === t[1] && k[2] === t[2], or per-coordinate === checks) instead of leaning on .includes() or === on the arrays themselves.

Quiz

1. Why is a triplet with any coordinate greater than target’s corresponding coordinate permanently unusable?

Merging only takes a max, which never decreases a value — an overshoot can never be undone by a later merge
Triplets with large values are always processed last, so they get skipped by convention
It’s an arbitrary rule with no connection to how the merge operation actually works

Answer: Merging only takes a max, which never decreases a value — an overshoot can never be undone by a later merge. The merge operation only ever takes a coordinate-wise maximum, which can never make a value smaller. So a triplet that already overshoots target on some coordinate will overshoot on that coordinate forever, no matter what it gets merged with — it can never contribute to reaching target.

2. Why does usability require ALL 3 coordinates to fit under target, rather than checking each coordinate across triplets independently?

A triplet is merged in as a whole — you can’t take only its safe coordinates and leave the unsafe one out
Checking all 3 together is just faster to type, not logically necessary
Only the first coordinate actually matters for correctness

Answer: A triplet is merged in as a whole — you can’t take only its safe coordinates and leave the unsafe one out. A triplet’s 3 coordinates are merged together as a unit — max is applied to all of them at once. You can’t selectively bring in only the coordinates that happen to fit; a single overshooting coordinate disqualifies the whole triplet from ever being merged in.

3. Why does marking a coordinate “achieved” require an exact match (===), not just ≤?

max() of values all below target’s coordinate stays below it — only an exact match can ever reach target exactly on that coordinate
It’s just a stylistic preference; ≤ would work identically
Exact match is only used to make the loop run faster

Answer: max() of values all below target’s coordinate stays below it — only an exact match can ever reach target exactly on that coordinate. max() of several values that are all strictly below target’s coordinate will still be strictly below it, never equal. So the only way a coordinate can end up exactly matching target after merging is if at least one contributing triplet already equals target on that coordinate before any merge happens.

4. Why is it enough to just count which coordinates get achieved, without tracking which specific triplets are merged together?

Merging any subset of usable, coordinate-matching triplets together reproduces target exactly — the specific combination doesn’t change the outcome
It happens to work on the LeetCode examples but isn’t actually guaranteed in general
Only a single triplet can ever be usable at a time, so there’s nothing to track

Answer: Merging any subset of usable, coordinate-matching triplets together reproduces target exactly — the specific combination doesn’t change the outcome. It doesn’t matter which usable triplets end up contributing which coordinate, or what order they’re checked in — the moment all 3 coordinates have SOME usable triplet matching them exactly, merging that whole subset together is guaranteed to produce target exactly, since usable triplets never exceed target on any coordinate.

5. What’s the practical time cost difference between the two solutions, and why?

Brute force costs O(n²) per round across possibly many rounds; optimal is a single O(n) pass with no merges performed
They’re identical — both are O(n) since they check the same triplets
Brute force is O(n) and optimal is O(n²), because tracking achieved coordinates requires nested loops

Answer: Brute force costs O(n²) per round across possibly many rounds; optimal is a single O(n) pass with no merges performed. Brute force actually performs merges — each round costs O(n²) to try every pair, and the known set can keep growing round after round before it stabilizes. The optimal solution looks at each triplet exactly once and never performs a merge, giving O(n) time and O(1) extra space.