Merge Triplets to Form Target Triplet
Decide whether merging triplets by element-wise max can produce a target: drop every triplet that overshoots it, merge all the rest.
Problem Understanding
Merge Triplets to Form Target Triplet: you can merge two triplets by taking the maximum in each position, and you may repeat this with any triplets you choose. Return whether you can end up with exactly target.
Examples: triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5] returns true; triplets = [[3,4,5],[4,5,6]], target = [3,2,5] returns false.
The Intuition: Values Only Go Up
A merge can only raise values, never lower them. That settles everything:
- A triplet with any value above the target is poison. Merge it and that position overshoots for good, so skip it.
- Every other triplet is harmless. It can raise a position to the target at most, so merging it never hurts.
- So merge all the harmless ones and check whether every position reached the target.
This is a greedy argument: taking every safe option is never worse than taking some of them. The same "filter out what can never work, then take everything else" shape appears in Partition Labels and Jump Game II, where the greedy choice is also justified by never closing off a better answer.
Interactive Walkthrough
RED = ABOVE THE TARGET
best = [0, 0, 0]
target
#0
#1
#2
best
merged
0
best
0,0,0
result
:
Target [2, 7, 5]. best = [0, 0, 0]: nothing merged yet
Next
[2, 5, 3]: every value ≤ the target, so it is safe to merge. best = max([0, 0, 0], [2, 5, 3]) = [2, 5, 3]
triplets
target
The target is on top and best at the bottom. Each row is a triplet: merged ones are tinted, and a skipped one is struck out with the value that broke it in red. Try One short: every triplet is safe, yet the last position never reaches 2.
Dry Run Table
Input: triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5].
| Triplet | All ≤ target? | Action | best |
|---|---|---|---|
| [2,5,3] | yes | merge | [2,5,3] |
| [1,8,4] | no, 8 > 7 | skip | [2,5,3] |
| [1,7,5] | yes | merge | [2,7,5] |
Answer: best = [2,7,5] equals the target, so true.
The Solution Template
One pass: filter by "no value above the target", merge with element-wise max, compare at the end.
Merge Triplets to Form Target Triplet Code
1var mergeTriplets = function(triplets, target) {2 const best = [0, 0, 0];3 for (const t of triplets) {4 if (t[0] <= target[0] && t[1] <= target[1] && t[2] <= target[2]) {5 for (let i = 0; i < 3; i++) best[i] = Math.max(best[i], t[i]);6 }7 }8 return best[0] === target[0] && best[1] === target[1] && best[2] === target[2];9};
Edge Cases & Common Mistakes
- Checking only one position: a triplet is unusable if any of its three values is above the target.
- Requiring an exact match per triplet: no single triplet has to equal the target; different triplets can supply different positions.
- Comparing arrays by reference: in JavaScript,
best === targetcompares references; compare the three values. - Early exit: you may return
trueas soon asbestequals the target; the answer is the same. - No safe triplets:
beststays[0, 0, 0], which never equals a target of positive values, so the answer isfalse.
Summary
Skip any triplet with a value above the target, merge every other triplet into best with element-wise max, and return whether best equals the target. O(n) time, O(1) space.
More practice: DSA interview questions with answers · patterns cheat sheet