Difficulty: MediumGreedy

Merge Triplets to Form Target Triplet

Problem in Plain English

You are given a list of integer triplets and a target triplet, and you may repeatedly replace any triplet with the element-wise maximum of two triplets. Return whether any sequence of such merges can produce the target triplet.

Problem Statement

You are given a 2D integer array triplets where triplets[i] = [a, b, c] is the ith triplet, and an integer array target = [x, y, z] describing the triplet you want to obtain.

In one operation you may pick two indices i and j with i != j and replace triplets[j] with [max(a_i, a_j), max(b_i, b_j), max(c_i, c_j)]. For example, merging [2, 5, 3] into [1, 7, 5] gives [max(2, 1), max(5, 7), max(3, 5)] = [2, 7, 5]. Return true if the target triplet can ever appear in triplets, otherwise return false.

Constraints

1 <= triplets.length <= 10^5
triplets[i].length == target.length == 3
1 <= a, b, c, x, y, z <= 1000

Examples

Example 1

Input: triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5]
Output: true

Merge [2,5,3] into [1,7,5] to get [max(2,1), max(5,7), max(3,5)] = [2,7,5], which equals the target.

Example 2

Input: triplets = [[3,4,5],[4,5,6]], target = [3,2,5]
Output: false

No triplet holds 2 in the middle position, so the target can never be formed.

Example 3

Input: triplets = [[2,5,3],[2,3,4],[1,2,5],[5,2,3]], target = [5,5,5]
Output: true

Merge [2,5,3] into [1,2,5] to get [2,5,5], then merge [2,5,5] into [5,2,3] to get [5,5,5].

Example 4

Input: triplets = [[2,7,5]], target = [2,7,5]
Output: true

The only row is already the target, so zero operations suffice. Two distinct indices are needed only when actually performing a merge.

Example 5

Input: triplets = [[2,8,5],[1,7,4]], target = [2,7,5]
Output: false

The first row supplies 2 and 5 but also overshoots the middle coordinate. The only safe row [1,7,4] cannot supply either missing value, so checking coordinates without filtering would give a false positive.

Intuition

A maximum can raise a coordinate but can never lower it. For target [2,7,5], row [1,8,4] is unusable because its middle 8 would survive every later merge. Safe rows [2,5,3] and [1,7,5] can be combined: one supplies the first coordinate 2, the other supplies 7 and 5. The useful question is whether safe rows collectively supply all three target values.

Approaches

Subset Enumeration

Solution Details

Reveal Subset Enumeration: intuition, complexity, and code

Intuition

Enumerate every choice of original rows and carry the coordinate-wise maximum of the selected rows. Maximum is associative and idempotent, so merge order and repeated use add no new possibilities. This baseline reveals an exponential bottleneck: n rows create up to 2 to the power n choices, so it is a teaching approach for small inputs, not a solution for the maximum input size.

Step-by-Step Logic

First scan for a row already equal to target; return true if found because zero merges suffice. Example 1 has no such row, so proceed to subset search.
Start a recursive search with index 0 and maximum [0,0,0]. At each call, test equality first; after all rows are decided, a remaining mismatch fails.
Try excluding the current row before including it. In Example 1, excluding [2,5,3] explores all subsets of the other two rows, none of which can provide first coordinate 2.
On a failed exclusion branch, allocate a fresh three-value maximum incorporating the current row. A new array preserves the state shared by other branches.
With [2,5,3] included, exclude [1,8,4], then try excluding and including [1,7,5]. Including the final row creates [2,7,5].
Return true immediately from that matching call and propagate it through the pending recursive calls. Example 1 does not explore branches that include both the first and overshooting second row.

Why It Works

By induction, any row produced by merges is the coordinate-wise maximum of a nonempty subset of original rows. Conversely, any nonempty subset can be merged into one of its row indices by merging each other selected row into that destination. The recursion explores both excluding and including every row, hence covers every subset. Its carried maximum is exactly the maximum of its selected prefix rows. Returning early on equality is sound because the selected subset already forms the target. The empty subset starts at [0,0,0] and cannot match a positive target.

Dry Run

Subset Enumeration: variable states at each step
Call order	Index	Maximum at entry	Branch from parent	Outcome
1	0	[0,0,0]	root	mismatch; exclude row 0
2	1	[0,0,0]	exclude row 0	mismatch; exclude row 1
3	2	[0,0,0]	exclude row 1	mismatch; exclude row 2
4	3	[0,0,0]	exclude row 2	end, false
5	3	[1,7,5]	include row 2	end, false
6	2	[1,8,4]	include row 1	mismatch; exclude row 2
7	3	[1,8,4]	exclude row 2	end, false
8	3	[1,8,5]	include row 2	end, false; calls 6 and 2 fail
9	1	[2,5,3]	include row 0	mismatch; exclude row 1
10	2	[2,5,3]	exclude row 1	mismatch; exclude row 2
11	3	[2,5,3]	exclude row 2	end, false
12	3	[2,7,5]	include row 2	equality, true; propagate to root

Complexity Analysis

Time Complexity

O(2^n)

Space Complexity

O(n)

Let n be the number of rows. A full binary decision tree has O(2^n) calls, each doing constant work; a worst-case failed search also allocates O(2^n) three-value arrays cumulatively. Only O(n) arrays and stack frames are live along a branch, so auxiliary space is O(n), excluding input. No input row is mutated. Recursive depth and exponential work make this baseline unsuitable for n = 100000, particularly Python recursion limits; use the greedy approach for the full contract. A preliminary O(n) exact-row scan handles an already-present target even at maximum n; it does not change the exponential worst-case bound.

Code

Solution.java

1class Solution {2    public boolean mergeTriplets(int[][] triplets, int[] target) {3        // A target already present needs no merge and avoids a deep search.4        for (int[] row : triplets) {5            if (row[0] == target[0] && row[1] == target[1] && row[2] == target[2]) return true;6        }7        return dfs(triplets, target, 0, new int[]{0, 0, 0});8    }9
10    private boolean dfs(int[][] triplets, int[] target, int index, int[] current) {11        if (current[0] == target[0] && current[1] == target[1] && current[2] == target[2]) {12            return true;13        }14        if (index == triplets.length) {15            return false;16        }17        // Exclusion shares current; inclusion below allocates a new state.18        if (dfs(triplets, target, index + 1, current)) {19            return true;20        }21        int[] next = new int[]{22            Math.max(current[0], triplets[index][0]),23            Math.max(current[1], triplets[index][1]),24            Math.max(current[2], triplets[index][2])25        };26        return dfs(triplets, target, index + 1, next);27    }28}

Hints

Hint 1

Merging takes element-wise maxima, so no coordinate can ever decrease once it grows past its target value.

Hint 2

Any triplet with a coordinate strictly larger than the matching target coordinate can never be used, so discard it outright.

Hint 3

After discarding those rows, check the three coordinates independently: some kept triplet must equal the target in each position.

Edge Cases

A triplet already equal to the target returns true without any merge taking place.
A coordinate value missing from every triplet, like the middle 2 in Example 2, makes the answer false no matter what is merged.
Duplicate triplets change nothing, since the element-wise maximum of identical rows is the same row.
If every row is unsafe, no witness flag can be set; the answer is false. A safe row with every coordinate strictly below the target also contributes no exact match.

Common Mistakes and Interview Tips

Merging every triplet including ones that overshoot the target, then watching the running maximum exceed target and calling it impossible.
Demanding one single triplet that matches all three coordinates instead of collecting the three matches independently across safe rows.
Setting flags from overshooting rows before filtering them, which reports true for targets that can never actually form.
The initial [0,0,0] is a search identity, not an actual row; its use relies on the strictly positive constraint.
Interview tip: explain why witnesses must come from safe rows, and why at most three distinct witness rows suffice. The recursion is only a baseline and cannot support maximum bounds.

Key Takeaway

When an operation only moves values in one direction, inputs that overshoot the goal are permanently useless: filter them out and the greedy choice becomes checking each coordinate independently.