#1899 Merge Triplets to Form Target Triplet

frequently reported atGoogle

the problem

In plain words

You get a list of triplets [a, b, c] and a target triplet [x, y, z]. One move picks two triplets i and j and replaces triplet j with their element-wise maximum: [max(aᵢ, aⱼ), max(bᵢ, bⱼ), max(cᵢ, cⱼ)]. You may make any number of moves. Return true if the target can end up as one of the triplets.

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

out true

Merge [2,5,3] and [1,7,5] → [2,7,5]. [1,8,4] would push y to 8, so leave it out.

in triplets = [[3,4,5],[4,5,6]], target = [3,2,5]

out false

Both triplets overshoot somewhere (4 > 2 and 4 > 3), and a max can never shrink a value.

in triplets = [[2,5,3],[2,3,4],[1,2,5],[5,2,3]], target = [5,5,5]

out true

Merge [2,5,3], [1,2,5] and [5,2,3] → [5,5,5].

1 ≤ triplets.length ≤ 10⁵
triplets[i].length == target.length == 3
1 ≤ every value ≤ 1000

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternGreedy choice

A merge can only make values bigger. So a triplet with any value above the target's can never be used. Every other triplet is harmless to merge, so the target is reachable exactly when the safe triplets together hit x, y and z.

solutions

From brute force to optimal

Any sequence of moves produces the element-wise max of some group. Try every group.

Recurse: take or skip each triplet, carrying the running max.
Return true when a non-empty group's max equals the target.

timeO(2ⁿ)

Every subset of n triplets. Only tiny inputs finish.

spaceO(n)

Recursion depth: one frame per triplet.

javajava.util.*

1class Solution {2    public boolean mergeTriplets(int[][] triplets, int[] target) {3        return tryFrom(triplets, target, 0, 0, 0, 0, false);4    }5 6    /** Choose or skip each triplet; the merge of a chosen group is its element-wise max. */7    private boolean tryFrom(int[][] t, int[] target, int i, int a, int b, int c, boolean picked) {8        if (picked && a == target[0] && b == target[1] && c == target[2]) return true;9        if (i == t.length) return false;10        return tryFrom(t, target, i + 1, Math.max(a, t[i][0]), Math.max(b, t[i][1]), Math.max(c, t[i][2]), true)11            || tryFrom(t, target, i + 1, a, b, c, picked);12    }13}

Ignore triplets that exceed the target anywhere. For the rest, record which target values they hit exactly.

For each triplet: if any value > the target's, skip it.
Otherwise mark x, y or z as matched where the values are equal.
Return true if all three are matched.

timeO(n)

One look at each triplet.

spaceO(1)

Three booleans.

javajava.util.*

1class Solution {2    public boolean mergeTriplets(int[][] triplets, int[] target) {3        boolean x = false, y = false, z = false; // which target values we have matched4        for (int[] t : triplets) {5            if (t[0] > target[0] || t[1] > target[1] || t[2] > target[2]) {6                continue; // overshoots somewhere: max can never come back down, so never use it7            }8            x |= t[0] == target[0]; // every safe triplet is harmless to merge,9            y |= t[1] == target[1]; // so just record what it contributes10            z |= t[2] == target[2];11        }12        return x && y && z;13    }14}

in the room

How to say it in the interview

talk track

Observe out loud: "max never decreases, so any value above the target is poison."
Then: "merging all the safe triplets can't overshoot, so I only need each of x, y and z to appear in some safe triplet."
Code it with three booleans in one pass.

traps

Counting a match from a triplet that overshoots elsewhere: [5, 9, 1] doesn't give you x = 5 when y must be 8.
Requiring one triplet to match all three values. Different triplets can supply x, y and z.

what they ask next

Follow-ups

Which triplets should you merge?

Every safe triplet that matches at least one target value. Their element-wise max is exactly the target.

k values per triplet instead of 3?

Same idea with a boolean[k]: O(n · k) time.

before you submit

Edge cases to test

The target is already in the list → true with zero moves.
The only triplet with x = target x overshoots y → false.
x, y and z come from three different triplets → true.

practise next