Loading…

mediumGreedyLC #1899Sometimes asked

Merge Triplets to Form Target Triplet

Q: How do you solve Merge Triplets to Form Target Triplet using the Brute Force — Enumerate Subsets and Merge approach?

When to use it: Mention briefly to frame the search space, then immediately note 2ⁿ subsets is hopeless for n = 10⁵ and pivot to the structural insight. Because merging is associative and commutative max, merging any chosen *set* of triplets yields exactly the component-wise maximum of that set. So 'can we obtain target?' is equivalent to 'does some subset of triplets have a component-wise max equal to `[x, y, z]`?'. The brute force answers that literally: enumerate every subset, fold it with max, and compare to target. **Why subsets and not sequences.** A first instinct is to model the *sequence* of merge operations, but order is irrelevant — `max(max(a, b), c) = max(a, max(b, c))`. Collapsing sequences to sets removes a huge amount of redundant exploration, but it still leaves `2ⁿ` subsets to try. **Why this is hopeless at scale.** With `n` up to `10⁵`, `2ⁿ` is beyond cosmic. Even at `n = 30` it's a billion subsets. We're not going to run this; we write it to *see the structure*: each subset is judged purely by, for each axis independently, the maximum value it contributes on that axis. **Why the structure begs for a greedy.** Notice the three axes are evaluated *independently* under max — the x-coordinate of the merged result depends only on the x-coordinates of the chosen triplets, never on their y or z. That independence is the crack we pry open: instead of choosing a subset jointly, we can reason axis-by-axis about which triplets are even allowed to participate. The next approach turns that into an O(n) test. **Why we keep the equivalence.** The subset framing is what justifies the greedy's correctness later: when we prove 'target is achievable iff each axis is covered by a safe triplet', we're really characterising exactly which subsets have component-wise max equal to target. Time complexity: O(2ⁿ · n). Space complexity: O(n).

LCPractice

Greedy Algorithms · 5 of 23 · 9 min

A triplet is an array of three integers. You are given a 2D integer array triplets, where triplets[i] = [aᵢ, bᵢ, cᵢ] describes the i-th triplet. You are also given an integer array target = [x, y, z] that describes the triplet you want to obtain.

To obtain target, you may apply the following operation any number of times:

Choose two indices (0-indexed) i and j (i != j) and update triplets[j] to become [max(aᵢ, aⱼ), max(bᵢ, bⱼ), max(cᵢ, cⱼ)].

Return true if it is possible to obtain the target triplet [x, y, z] as an element of triplets, or false otherwise.

In plain English

You can repeatedly fuse triplets by taking the per-component maximum, which only ever raises values. The question is whether some sequence of fusions can produce exactly target = [x, y, z]. Because order of merges doesn't matter and max is associative, this reduces to: is there a set of triplets whose component-wise max equals target?

Examples

Example 1

Input: triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5]
Output: true
Note: [2,5,3] gives x=2, [1,7,5] gives y=7 and z=5. All three safe (≤ target). Merging them: [max(2,1), max(5,7), max(3,5)] = [2,7,5] = target.

Example 2

Input: triplets = [[3,4,5],[4,5,6]], target = [3,2,5]
Output: false
Note: Every triplet has a component exceeding target (b=4>2, etc.), so no safe triplet exists and the y-axis (2) can never be matched.

Example 3

Input: triplets = [[2,5,3],[2,3,4],[1,2,5],[5,2,3]], target = [5,5,5]
Output: true
Note: Safe triplets (all ≤ [5,5,5]): [2,5,3] hits y=5, [1,2,5] hits z=5, [5,2,3] hits x=5. Merging the three reproduces [5,5,5]. ([2,3,4] is also safe but unneeded.)

Constraints

1 ≤ triplets.length ≤ 10⁵
triplets[i].length == target.length == 3
1 ≤ aᵢ, bᵢ, cᵢ, x, y, z ≤ 1000
Merging replaces a triplet with the component-wise max of two triplets

Clarifying questions4First question: Does the order of merges matter?Explore questions

Q1.Does the order of merges matter?
No — component-wise max is associative and commutative, so any sequence of merges over a chosen set yields the same result: the per-component max of that set. That's why we can think in terms of sets, not sequences.
Q2.Can merging ever decrease a component?
Never. Each merge takes a max, so every component is monotone non-decreasing. That monotonicity is the entire basis for filtering out triplets that exceed the target.
Q3.Do I have to use a triplet exactly equal to target, or build it up?
You can build it up from several triplets, each contributing the target value on at least one axis — as long as none of them exceeds the target anywhere.
Q4.Are all values positive?
Yes, everything is in [1, 1000]. No negatives to complicate the max reasoning.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Merging two triplets replaces them with their component-wise max, so values only ever grow. The brute force tries subsets and merges them in exponential time. The greedy observation: any triplet with a component greater than the corresponding target value is poison — using it overshoots that axis forever. So keep only the 'safe' triplets (every component ≤ target), and check that for each of the three axes some safe triplet already equals the target there. If all three axes are hit, return true. One pass, O(n) time, O(1) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you reason about the monotonicity of the merge (max only increases) to conclude that overshooting triplets are unusable, and whether you then decompose a seemingly-coupled 3D problem into three independent per-axis coverage checks.

Where candidates slip

Trying to enumerate which subset of triplets to merge (exponential), or forgetting to filter out triplets that exceed the target on some axis and then merging them — which silently overshoots and corrupts the result.

How to stand out

State the monotonicity argument explicitly — 'merge is component-wise max, so a too-big component can never come back down, hence any triplet exceeding target is poison' — then prove both directions: every usable triplet is safe, and merging all safe triplets reproduces target exactly when each axis is covered.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Enumerate Subsets and Merge	`O(2ⁿ · n)`	`O(n)`	Mention briefly to frame the search space, then immediately note 2ⁿ subsets is hopeless for n = 10⁵ and pivot to the structural insight.	Read
2	Greedy — Filter Overshooters, Cover Each Axis (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Frame it as 'merge is monotone max, so any triplet bigger than target on any axis is poison — keep the rest and check each axis is hit'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewCan merges produce target = [x,y,z]?How to choose what to merge?Try every subsetOptimalExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Enumerate Subsets and Merge

TimeO(2ⁿ · n)SpaceO(n)

Mention briefly to frame the search space, then immediately note 2ⁿ subsets is hopeless for n = 10⁵ and pivot to the structural insight.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Since merge order doesn't matter, the result of merging a chosen set is just the component-wise max over that set. So the question is: does some subset have component-wise max equal to target?

2Hint 2Explore hint

The literal approach enumerates every subset, computes its component-wise max, and checks against target.

3Hint 3Explore hint

That's 2ⁿ subsets — astronomically too slow for n up to 10⁵. The point of writing it is to expose the structure that makes it collapsible.

A · Core idea

Because merging is associative and commutative max, merging any chosen set of triplets yields exactly the component-wise maximum of that set. So 'can we obtain target?' is equivalent to 'does some subset of triplets have a component-wise max equal to [x, y, z]?'. The brute force answers that literally: enumerate every subset, fold it with max, and compare to target.

Why subsets and not sequences. A first instinct is to model the sequence of merge operations, but order is irrelevant — max(max(a, b), c) = max(a, max(b, c)). Collapsing sequences to sets removes a huge amount of redundant exploration, but it still leaves 2ⁿ subsets to try.

Why this is hopeless at scale. With n up to 10⁵, 2ⁿ is beyond cosmic. Even at n = 30 it's a billion subsets. We're not going to run this; we write it to see the structure: each subset is judged purely by, for each axis independently, the maximum value it contributes on that axis.

Why the structure begs for a greedy. Notice the three axes are evaluated independently under max — the x-coordinate of the merged result depends only on the x-coordinates of the chosen triplets, never on their y or z. That independence is the crack we pry open: instead of choosing a subset jointly, we can reason axis-by-axis about which triplets are even allowed to participate. The next approach turns that into an O(n) test.

Why we keep the equivalence. The subset framing is what justifies the greedy's correctness later: when we prove 'target is achievable iff each axis is covered by a safe triplet', we're really characterising exactly which subsets have component-wise max equal to target.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

triplets = [[2,5,3],[1,7,5]], target = [2,7,5]

{[2,5,3]}

max = [2,5,3]

State≠ target

Final resulttrue

C · Code with teaching comments

Reference implementation previewpublic boolean mergeTriplets(int[][] triplets, int[] target) { int n = triplets.length; for (int mask = 1; mask < (1 << n); mask++) { int a = 0, b = 0, c = 0; for (int i = 0; i < n; i++) {Explore the full code

solution.javaJava

Brute Force — Enumerate Subsets and Merge — reference

3 teaching notes

1
public boolean mergeTriplets(int[][] triplets, int[] target) {
2
    int n = triplets.length;
3
    // Iterate every non-empty subset of triplets as a bitmask — the 2ⁿ blow-up.
4
    for (int mask = 1; mask < (1 << n); mask++) {
5
        int a = 0, b = 0, c = 0;
6
        for (int i = 0; i < n; i++) {
7
            // Triplet i is in this subset; fold it into the running component-wise max.
8
            if ((mask & (1 << i)) != 0) {
9
                a = Math.max(a, triplets[i][0]);
10
                b = Math.max(b, triplets[i][1]);
11
                c = Math.max(c, triplets[i][2]);
12
            }
13
        }
14
        // This subset's merge equals target — achievable.
15
        if (a == target[0] && b == target[1] && c == target[2]) return true;
16
    }
17
    return false;
18
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.18 lines

D · Why it works and complexityO(2ⁿ · n) timeO(n) spaceOpen the invariant and proofExplore the proof

Two reductions shrink the problem: merges → sets (order doesn't matter under max), and then sets → per-axis coverage (max evaluates each coordinate independently). The exponential brute force exists only to surface those two facts; once you see them, no enumeration is needed.

ComplexityO(2ⁿ · n) time, O(n) space — There are 2ⁿ subsets; computing the component-wise max of a subset costs up to O(n). The product O(2ⁿ · n) is exponential and infeasible beyond tiny n.

E · Edge cases and pitfalls3Modelling merge sequences instead of subsets — explodes the search even further for no reason.Explore edge cases

Pitfalls

Modelling merge sequences instead of subsets — explodes the search even further for no reason.
Believing 2ⁿ could pass — it can't beyond ~n=20; this is illustrative only.
Including a triplet that overshoots target and still expecting a match — the merged max will exceed target.

03.2

Approach 2 of 2 · Optimal

Greedy — Filter Overshooters, Cover Each Axis (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Frame it as 'merge is monotone max, so any triplet bigger than target on any axis is poison — keep the rest and check each axis is hit'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Merging takes a max, so values only ever go up. If a triplet has a component larger than target's, including it overshoots that axis — and you can never bring it back down. What does that say about which triplets are usable?

2Hint 2Explore hint

Keep only 'safe' triplets: those with all three components ≤ target. Merging any collection of safe triplets can never exceed target on any axis.

3Hint 3Explore hint

Among safe triplets, you need each axis to actually reach the target value. Track three booleans: does some safe triplet equal target on x? on y? on z? Return true iff all three are covered.

A · Core idea

Scan the triplets once. Call a triplet safe if a ≤ x and b ≤ y and c ≤ z — every component is within target. For each safe triplet, mark the axes on which it equals the target (a == x marks axis 0, and so on). After the pass, return true iff all three axes were marked.

Why overshooting triplets are poison — the monotonicity argument. Merging is component-wise max, so once any component exceeds its target value, no further merge can reduce it — max never decreases. Therefore if you ever fold a triplet with, say, a > x into your working set, the x-component is stuck above x forever and you can never equal target. So any triplet exceeding target on any axis is permanently unusable and must be discarded. Only safe triplets can participate.

Why it's free to merge all safe triplets — and why that proves sufficiency. Suppose for each axis there's a safe triplet equalling target there. Merge all safe triplets together. On axis x, the result is the max of a over all safe triplets; since every safe triplet has a ≤ x, that max is ≤ x, and since some safe triplet has a == x, the max is exactly x. The identical argument gives y on axis 2 and z on axis 3. So the merged triplet is exactly [x, y, z] — target is achievable. Crucially, throwing extra safe triplets into the merge can never hurt: they're all bounded by target, so they can't push any axis past it. That's why greed (take every safe triplet) is risk-free.

Why the condition is also necessary — the contradiction argument. Suppose target is achievable but some axis, say x, is not covered by any safe triplet. The achieving subset's component-wise max must equal x on that axis, so some triplet in the subset has a == x. For the subset to produce target, every triplet in it must be safe (an overshooter would have pushed some axis past target, as argued). So that triplet is a safe triplet with a == x — contradicting 'no safe triplet covers x'. Hence every axis covered by the achieving solution is covered by a safe triplet, and our three booleans capture exactly that. Both directions together make the three-way coverage check an exact characterisation, not a heuristic.

Why the axes can be treated independently. Component-wise max evaluates each coordinate in isolation — the x-result depends only on x-values. So 'cover x', 'cover y', 'cover z' are three independent sub-questions, and a single triplet may help with several at once. That independence is what lets one linear pass with three flags replace the exponential subset search.

Why this beats the brute force. The brute force searches 2ⁿ subsets; the greedy uses monotonicity to forbid overshooters and coordinate-independence to split into three trivial coverage checks, collapsing O(2ⁿ·n) to O(n) and O(n) space to O(1).

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Interactive diagram

Why overshooters are poison

[2,5,3]

Active call / nodeSupporting contextReturned stateNot active

Merge is component-wise max, so a component above target can never come back down — such triplets are filtered before any coverage check.

Final resulttrue

C · Code with teaching comments

solution.javaJava

Greedy — Filter Overshooters, Cover Each Axis (Optimal) — optimal

4 teaching notes

1
public boolean mergeTriplets(int[][] triplets, int[] target) {
2
    // One flag per axis: has some safe triplet equalled target on x / y / z?
3
    boolean[] hit = new boolean[3];
4
    for (int[] t : triplets) {
5
        // Safety gate — any component above target makes this triplet poison, so skip
6
        // it entirely.
7
        if (t[0] <= target[0] && t[1] <= target[1] && t[2] <= target[2]) {
8
            for (int k = 0; k < 3; k++) {
9
                // A safe triplet that matches target on axis k covers that axis.
10
                if (t[k] == target[k]) hit[k] = true;
11
            }
12
        }
13
    }
14
    // Achievable iff every axis is covered by some safe triplet.
15
    return hit[0] && hit[1] && hit[2];
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

The whole problem hinges on one property: the combine operation (max) is monotone, so anything that overshoots the target can only ever stay overshot — it's strictly harmful and gets filtered. Once the poison is gone, the remaining triplets can all be merged with impunity, and a multi-dimensional target decomposes into independent per-coordinate coverage. Spotting 'monotone combine ⇒ drop overshooters' is the transferable trick.

ComplexityO(n) time, O(1) space — One pass over n triplets with O(1) work each (three comparisons to test safety, three to update coverage) gives O(n) time; we keep three booleans, so O(1) space.

E · Edge cases and pitfalls6triplets = [[1,1,1]], target = [1,1,1] — Single safe triplet equals target on all three axes → hit = [T,T,T] → true.Explore edge cases

Edge cases handled

triplets = [[1,1,1]], target = [1,1,1]Single safe triplet equals target on all three axes → hit = [T,T,T] → true.
triplets = [[3,4,5],[4,5,6]], target = [3,2,5]Both overshoot (b=4>2, b=5>2) so no safe triplet exists; y-axis (2) never covered → false.
triplets = [[1,3,4],[2,5,8]], target = [2,5,8][1,3,4] safe but matches no axis; [2,5,8] safe and equals target on all axes → true.

Pitfalls

Forgetting the safety filter and merging overshooting triplets — silently exceeds target on some axis.
Requiring a single triplet to equal target on all axes instead of covering axes across several safe triplets.
Returning true as soon as one axis is hit — all three must be covered.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic boolean mergeTriplets(int[][] triplets, int[] target) { boolean[] hit = new boolean[3]; for (int[] t : triplets) { if (t[0] <= target[0] && t[1] <= target[1] && t[2] <= target[2]) { for (int k = 0; k < 3; k++) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Skipping the overshoot filter

If you fold in a triplet with a component above target, the component-wise max permanently exceeds target on that axis — yet a naive coverage check might still report success.

Explore the code comparison

Don't write this

hit = [False, False, False]
for t in triplets:
    for k in range(3):
        if t[k] == target[k]:   # no safety check!
            hit[k] = True
return all(hit)

Write this instead

hit = [False, False, False]
for t in triplets:
    if t[0] <= target[0] and t[1] <= target[1] and t[2] <= target[2]:
        for k in range(3):
            if t[k] == target[k]:
                hit[k] = True
return all(hit)

Demanding a single all-axis match

Target can be assembled from several safe triplets, each contributing one or more axes. Requiring one triplet to equal target everywhere rejects valid inputs.

Explore the code comparison

Don't write this

for (int[] t : triplets) {
    if (t[0] == target[0] && t[1] == target[1] && t[2] == target[2])
        return true; // misses multi-triplet builds
}
return false;

Write this instead

boolean[] hit = new boolean[3];
for (int[] t : triplets) {
    if (t[0] <= target[0] && t[1] <= target[1] && t[2] <= target[2])
        for (int k = 0; k < 3; k++) if (t[k] == target[k]) hit[k] = true;
}
return hit[0] && hit[1] && hit[2];

Returning on the first axis covered

Coverage of one axis says nothing about the other two. The answer is the conjunction of all three coverage flags, checked after the full pass.

Explore the code comparison

Don't write this

for t in triplets:
    if t[0] <= target[0] and t[1] <= target[1] and t[2] <= target[2]:
        if t[0] == target[0]:
            return True   # only checked axis x

Write this instead

# accumulate all three flags across the whole pass
return all(hit)

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Greedy filter-then-cover — discard overshooters, hit each axis

Code pattern to memorize

hit = [False, False, False]
for a, b, c in triplets:
    if a <= tx and b <= ty and c <= tz:   # safe triplet
        if a == tx: hit[0] = True
        if b == ty: hit[1] = True
        if c == tz: hit[2] = True
return all(hit)

Rules to remember

1Merging is component-wise max, so a value can only increase — you can never bring an overshot axis back down.
2A triplet with any component > target is unusable: include it and that axis overshoots permanently. Filter it out.
3Among the safe triplets (all three components ≤ target), you need each axis k to be exactly equalled by some safe triplet.
4It's always safe to merge every safe triplet — none can push an axis past target, so greediness costs nothing.
5Track three booleans (or a set) for 'axis x/y/z reached'; return true iff all three are hit.
6No need to actually merge or build subsets — the question reduces to three independent coverage checks.

Use this pattern when

Combine operation is monotone (max/OR/union) so values only grow
A target must be matched component-wise across independent axes
Elements that exceed the target on any axis are strictly harmful and can be dropped
You can decompose 'can we build X' into per-coordinate coverage checks

Choose another pattern when

The combine operation can decrease a value (min, subtraction) → filtering logic flips or breaks
Axes are coupled (a choice helping one axis forces another past target) → can't treat coordinates independently
You must return the actual subset used → track contributors, not just booleans
Targets aren't a fixed point of the operation → reframe the problem

Interview takeaway

Merge Triplets is the cleanest 'monotone combine + filter the poison' greedy: because max only grows, any triplet exceeding the target is forbidden, and once you keep only safe ones you can merge them all freely — the problem collapses to three independent 'did any safe triplet equal the target here?' checks. The same 'drop anything that can only overshoot' idea recurs wherever the combine operation is monotone.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternCanonical 'monotone combine + filter the poison' greedy: because merging is component-wise max (values only grow), any triplet exceeding the target on any axis is permanently unusable and is discarded, after which a multi-axis target decomposes into independent per-coordinate coverage checks. Recognise it whenever the combine operation is monotone and a target must be matched coordinate-by-coordinate.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Check if All the Integers in a Range Are Covered
Coming soon
Coverage thinking on a 1D range — mark covered points, verify full coverage.
Path Crossing
Coming soon
Track visited coordinates in a set — sibling 'coverage via membership' check.
Partition Labels
Coming soon
Greedy that tracks the max reach of each label — same 'monotone boundary' flavour.
Maximum Performance of a Team
Coming soon
Greedy over a monotone dimension (efficiency) with a heap — pick what can only help.

Same pattern

←

Hand of Straights

Continue · Next problem

Jumping on the Clouds

mediumGreedyLC #1899Sometimes asked

Merge Triplets to Form Target Triplet

LCPractice

Greedy Algorithms · 5 of 23 · 9 min

To obtain target, you may apply the following operation any number of times:

Choose two indices (0-indexed) i and j (i != j) and update triplets[j] to become [max(aᵢ, aⱼ), max(bᵢ, bⱼ), max(cᵢ, cⱼ)].

Return true if it is possible to obtain the target triplet [x, y, z] as an element of triplets, or false otherwise.

In plain English

Examples

Example 1

Input: triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5]
Output: true
Note: [2,5,3] gives x=2, [1,7,5] gives y=7 and z=5. All three safe (≤ target). Merging them: [max(2,1), max(5,7), max(3,5)] = [2,7,5] = target.

Example 2

Input: triplets = [[3,4,5],[4,5,6]], target = [3,2,5]
Output: false
Note: Every triplet has a component exceeding target (b=4>2, etc.), so no safe triplet exists and the y-axis (2) can never be matched.

Example 3

Input: triplets = [[2,5,3],[2,3,4],[1,2,5],[5,2,3]], target = [5,5,5]
Output: true
Note: Safe triplets (all ≤ [5,5,5]): [2,5,3] hits y=5, [1,2,5] hits z=5, [5,2,3] hits x=5. Merging the three reproduces [5,5,5]. ([2,3,4] is also safe but unneeded.)

Constraints

1 ≤ triplets.length ≤ 10⁵
triplets[i].length == target.length == 3
1 ≤ aᵢ, bᵢ, cᵢ, x, y, z ≤ 1000
Merging replaces a triplet with the component-wise max of two triplets

Clarifying questions4First question: Does the order of merges matter?Explore questions

Q1.Does the order of merges matter?
No — component-wise max is associative and commutative, so any sequence of merges over a chosen set yields the same result: the per-component max of that set. That's why we can think in terms of sets, not sequences.
Q2.Can merging ever decrease a component?
Never. Each merge takes a max, so every component is monotone non-decreasing. That monotonicity is the entire basis for filtering out triplets that exceed the target.
Q3.Do I have to use a triplet exactly equal to target, or build it up?
You can build it up from several triplets, each contributing the target value on at least one axis — as long as none of them exceeds the target anywhere.
Q4.Are all values positive?
Yes, everything is in [1, 1000]. No negatives to complicate the max reasoning.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Enumerate Subsets and Merge	`O(2ⁿ · n)`	`O(n)`	Mention briefly to frame the search space, then immediately note 2ⁿ subsets is hopeless for n = 10⁵ and pivot to the structural insight.	Read
2	Greedy — Filter Overshooters, Cover Each Axis (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Frame it as 'merge is monotone max, so any triplet bigger than target on any axis is poison — keep the rest and check each axis is hit'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Enumerate Subsets and Merge

TimeO(2ⁿ · n)SpaceO(n)

Mention briefly to frame the search space, then immediately note 2ⁿ subsets is hopeless for n = 10⁵ and pivot to the structural insight.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Since merge order doesn't matter, the result of merging a chosen set is just the component-wise max over that set. So the question is: does some subset have component-wise max equal to target?

2Hint 2Explore hint

The literal approach enumerates every subset, computes its component-wise max, and checks against target.

3Hint 3Explore hint

That's 2ⁿ subsets — astronomically too slow for n up to 10⁵. The point of writing it is to expose the structure that makes it collapsible.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

triplets = [[2,5,3],[1,7,5]], target = [2,7,5]

{[2,5,3]}

max = [2,5,3]

State≠ target

Final resulttrue

C · Code with teaching comments

solution.javaJava

Brute Force — Enumerate Subsets and Merge — reference

3 teaching notes

1
public boolean mergeTriplets(int[][] triplets, int[] target) {
2
    int n = triplets.length;
3
    // Iterate every non-empty subset of triplets as a bitmask — the 2ⁿ blow-up.
4
    for (int mask = 1; mask < (1 << n); mask++) {
5
        int a = 0, b = 0, c = 0;
6
        for (int i = 0; i < n; i++) {
7
            // Triplet i is in this subset; fold it into the running component-wise max.
8
            if ((mask & (1 << i)) != 0) {
9
                a = Math.max(a, triplets[i][0]);
10
                b = Math.max(b, triplets[i][1]);
11
                c = Math.max(c, triplets[i][2]);
12
            }
13
        }
14
        // This subset's merge equals target — achievable.
15
        if (a == target[0] && b == target[1] && c == target[2]) return true;
16
    }
17
    return false;
18
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.18 lines

D · Why it works and complexityO(2ⁿ · n) timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3Modelling merge sequences instead of subsets — explodes the search even further for no reason.Explore edge cases

Pitfalls

Modelling merge sequences instead of subsets — explodes the search even further for no reason.
Believing 2ⁿ could pass — it can't beyond ~n=20; this is illustrative only.
Including a triplet that overshoots target and still expecting a match — the merged max will exceed target.

03.2

Approach 2 of 2 · Optimal

Greedy — Filter Overshooters, Cover Each Axis (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Frame it as 'merge is monotone max, so any triplet bigger than target on any axis is poison — keep the rest and check each axis is hit'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

2Hint 2Explore hint

Keep only 'safe' triplets: those with all three components ≤ target. Merging any collection of safe triplets can never exceed target on any axis.

3Hint 3Explore hint

Among safe triplets, you need each axis to actually reach the target value. Track three booleans: does some safe triplet equal target on x? on y? on z? Return true iff all three are covered.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Interactive diagram

Why overshooters are poison

[2,5,3]

Active call / nodeSupporting contextReturned stateNot active

Merge is component-wise max, so a component above target can never come back down — such triplets are filtered before any coverage check.

Final resulttrue

C · Code with teaching comments

solution.javaJava

Greedy — Filter Overshooters, Cover Each Axis (Optimal) — optimal

4 teaching notes

1
public boolean mergeTriplets(int[][] triplets, int[] target) {
2
    // One flag per axis: has some safe triplet equalled target on x / y / z?
3
    boolean[] hit = new boolean[3];
4
    for (int[] t : triplets) {
5
        // Safety gate — any component above target makes this triplet poison, so skip
6
        // it entirely.
7
        if (t[0] <= target[0] && t[1] <= target[1] && t[2] <= target[2]) {
8
            for (int k = 0; k < 3; k++) {
9
                // A safe triplet that matches target on axis k covers that axis.
10
                if (t[k] == target[k]) hit[k] = true;
11
            }
12
        }
13
    }
14
    // Achievable iff every axis is covered by some safe triplet.
15
    return hit[0] && hit[1] && hit[2];
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6triplets = [[1,1,1]], target = [1,1,1] — Single safe triplet equals target on all three axes → hit = [T,T,T] → true.Explore edge cases

Edge cases handled

triplets = [[1,1,1]], target = [1,1,1]Single safe triplet equals target on all three axes → hit = [T,T,T] → true.
triplets = [[3,4,5],[4,5,6]], target = [3,2,5]Both overshoot (b=4>2, b=5>2) so no safe triplet exists; y-axis (2) never covered → false.
triplets = [[1,3,4],[2,5,8]], target = [2,5,8][1,3,4] safe but matches no axis; [2,5,8] safe and equals target on all axes → true.

Pitfalls

Forgetting the safety filter and merging overshooting triplets — silently exceeds target on some axis.
Requiring a single triplet to equal target on all axes instead of covering axes across several safe triplets.
Returning true as soon as one axis is hit — all three must be covered.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Skipping the overshoot filter

If you fold in a triplet with a component above target, the component-wise max permanently exceeds target on that axis — yet a naive coverage check might still report success.

Explore the code comparison

Don't write this

hit = [False, False, False]
for t in triplets:
    for k in range(3):
        if t[k] == target[k]:   # no safety check!
            hit[k] = True
return all(hit)

Write this instead

hit = [False, False, False]
for t in triplets:
    if t[0] <= target[0] and t[1] <= target[1] and t[2] <= target[2]:
        for k in range(3):
            if t[k] == target[k]:
                hit[k] = True
return all(hit)

Demanding a single all-axis match

Target can be assembled from several safe triplets, each contributing one or more axes. Requiring one triplet to equal target everywhere rejects valid inputs.

Explore the code comparison

Don't write this

for (int[] t : triplets) {
    if (t[0] == target[0] && t[1] == target[1] && t[2] == target[2])
        return true; // misses multi-triplet builds
}
return false;

Write this instead

boolean[] hit = new boolean[3];
for (int[] t : triplets) {
    if (t[0] <= target[0] && t[1] <= target[1] && t[2] <= target[2])
        for (int k = 0; k < 3; k++) if (t[k] == target[k]) hit[k] = true;
}
return hit[0] && hit[1] && hit[2];

Returning on the first axis covered

Coverage of one axis says nothing about the other two. The answer is the conjunction of all three coverage flags, checked after the full pass.

Explore the code comparison

Don't write this

for t in triplets:
    if t[0] <= target[0] and t[1] <= target[1] and t[2] <= target[2]:
        if t[0] == target[0]:
            return True   # only checked axis x

Write this instead

# accumulate all three flags across the whole pass
return all(hit)

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Greedy filter-then-cover — discard overshooters, hit each axis

Code pattern to memorize

hit = [False, False, False]
for a, b, c in triplets:
    if a <= tx and b <= ty and c <= tz:   # safe triplet
        if a == tx: hit[0] = True
        if b == ty: hit[1] = True
        if c == tz: hit[2] = True
return all(hit)

Rules to remember

1Merging is component-wise max, so a value can only increase — you can never bring an overshot axis back down.
2A triplet with any component > target is unusable: include it and that axis overshoots permanently. Filter it out.
3Among the safe triplets (all three components ≤ target), you need each axis k to be exactly equalled by some safe triplet.
4It's always safe to merge every safe triplet — none can push an axis past target, so greediness costs nothing.
5Track three booleans (or a set) for 'axis x/y/z reached'; return true iff all three are hit.
6No need to actually merge or build subsets — the question reduces to three independent coverage checks.

Use this pattern when

Combine operation is monotone (max/OR/union) so values only grow
A target must be matched component-wise across independent axes
Elements that exceed the target on any axis are strictly harmful and can be dropped
You can decompose 'can we build X' into per-coordinate coverage checks

Choose another pattern when

The combine operation can decrease a value (min, subtraction) → filtering logic flips or breaks
Axes are coupled (a choice helping one axis forces another past target) → can't treat coordinates independently
You must return the actual subset used → track contributors, not just booleans
Targets aren't a fixed point of the operation → reframe the problem

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Check if All the Integers in a Range Are Covered
Coming soon
Coverage thinking on a 1D range — mark covered points, verify full coverage.
Path Crossing
Coming soon
Track visited coordinates in a set — sibling 'coverage via membership' check.
Partition Labels
Coming soon
Greedy that tracks the max reach of each label — same 'monotone boundary' flavour.
Maximum Performance of a Team
Coming soon
Greedy over a monotone dimension (efficiency) with a heap — pick what can only help.

Same pattern

←

Hand of Straights

Continue · Next problem

Jumping on the Clouds