Skip to main content
CodePeetCodePeet
CodePeet 150

Merge Triplets to Form Target Triplet

MEDIUMProblemSolveExternal Links

Description

You are given a 2D array of integers triplets, where each triplets[i] = [a_i, b_i, c_i] is a triplet of three values. You are also given an integer array target = [x, y, z] representing the triplet you want to obtain.

You may apply the following merge operation on triplets any number of times (including zero):

  • Choose two different indices i and j.
  • Update triplets[j] to become [max(a_i, a_j), max(b_i, b_j), max(c_i, c_j)].

In other words, you replace triplets[j] with the element-wise maximum of triplets[i] and triplets[j].

Return true if it is possible to make target appear as an element of triplets after any number of operations, or false otherwise.

Key observation: The merge operation can only increase (or keep equal) the values in a triplet — it can never decrease them, since we take the maximum at each position.

Examples

Example 1:

Input: triplets = [[1,2,3],[7,1,1]], target = [7,2,3]

Output: true

Explanation: Choose triplets[0] = [1,2,3] and triplets[1] = [7,1,1]. Merge them into triplets[1]:

  • [max(1,7), max(2,1), max(3,1)] = [7, 2, 3]

Now triplets[1] = [7,2,3], which equals the target.

Example 2:

Input: triplets = [[2,5,6],[1,4,4],[5,7,5]], target = [5,4,6]

Output: false

Explanation: No sequence of merge operations can produce [5,4,6].

  • [2,5,6] has 5 > 4 in position 2 — using it would force position 2 to be at least 5, overshooting the target's 4.
  • [5,7,5] has 7 > 4 in position 2 — same issue.
  • [1,4,4] is the only safe triplet, but its maximum is [1,4,4], which can never reach 5 in position 1.
  • Since no combination of safe triplets can produce a first-position value of 5, the answer is false.

Constraints

  • 1 <= triplets.length <= 10^5
  • triplets[i].length == 3
  • 1 <= a_i, b_i, c_i, x, y, z <= 1000

Editorial

Brute Force - Subset Enumeration

Intuition

The most direct approach is to try every possible combination of triplets and see if any combination, when merged together, produces exactly the target.

Here's the key observation: if we pick any subset of triplets and merge them all together, the result is simply the element-wise maximum across all triplets in that subset. The order of merging doesn't matter — taking the max is associative and commutative.

For example, merging [2,5,3], [1,7,5] in any order gives [max(2,1), max(5,7), max(3,5)] = [2,7,5].

So the problem reduces to: does any non-empty subset of triplets have an element-wise max equal to the target?

We can enumerate all 2^n - 1 non-empty subsets using bitmask enumeration. For each subset, compute the element-wise max and compare it to the target. If any matches, return true.

Limitation: This approach has O(2^n) time complexity, which is only feasible for very small n (roughly n ≤ 20). For the actual constraints (n up to 10^5), this approach is far too slow — but it helps us understand the problem structure before deriving the optimal solution.

Step-by-Step

Let's trace through triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5].

With n = 3 triplets, there are 2^3 - 1 = 7 non-empty subsets to check.

Subset {0}: [2,5,3]

  • Element-wise max: [2,5,3]
  • Compare to [2,7,5]: position 0: 2=2 ✓, position 1: 5≠7 ✗ → No match.

Subset {1}: [1,8,4]

  • Element-wise max: [1,8,4]
  • Compare to [2,7,5]: position 0: 1≠2 ✗ → No match.
  • Note: position 1 has 8 > 7 — this triplet overshoots the target.

Subset {2}: [1,7,5]

  • Element-wise max: [1,7,5]
  • Compare to [2,7,5]: position 0: 1≠2 ✗ → No match.

Subset {0,1}: max([2,5,3], [1,8,4]) = [2,8,4]

  • Compare to [2,7,5]: position 1: 8 > 7 → OVERSHOOT! Triplet [1,8,4] "poisons" the merge.

Subset {0,2}: max([2,5,3], [1,7,5]) = [2,7,5]

  • Compare to [2,7,5]: position 0: 2=2 ✓, position 1: 7=7 ✓, position 2: 5=5 ✓ → MATCH!
  • Return true.

We found the answer at subset {0,2}, but had to check 5 subsets. In the worst case, we'd check all 7. For large n, this exponential search is impractical.

Set up brute force — Set up brute force. Target is [2,7,5]. We'll try all non-empty subsets of 3 triplets.

Algorithm

  1. For each non-empty subset of triplets (represented by bitmask 1 to 2^n - 1):
    • Initialize merged = [0, 0, 0].
    • For each triplet in the subset, compute element-wise max: merged[j] = max(merged[j], triplets[i][j]) for j in {0, 1, 2}.
    • If merged == target, return true.
  2. If no subset matches, return false.

Code

class Solution {
public:
    bool mergeTriplets(vector<vector<int>>& triplets,
                       vector<int>& target) {
        int n = triplets.size();
        for (int mask = 1; mask < (1 << n); mask++) {
            vector<int> merged(3, 0);
            for (int i = 0; i < n; i++) {
                if (mask & (1 << i)) {
                    for (int j = 0; j < 3; j++) {
                        merged[j] = max(merged[j],
                                       triplets[i][j]);
                    }
                }
            }
            if (merged == target) return true;
        }
        return false;
    }
};
class Solution:
    def mergeTriplets(self, triplets: List[List[int]],
                      target: List[int]) -> bool:
        n = len(triplets)
        for mask in range(1, 1 << n):
            merged = [0, 0, 0]
            for i in range(n):
                if mask & (1 << i):
                    for j in range(3):
                        merged[j] = max(merged[j],
                                       triplets[i][j])
            if merged == target:
                return True
        return False
class Solution {
    public boolean mergeTriplets(int[][] triplets,
                                 int[] target) {
        int n = triplets.length;
        for (int mask = 1; mask < (1 << n); mask++) {
            int[] merged = new int[3];
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    for (int j = 0; j < 3; j++) {
                        merged[j] = Math.max(merged[j],
                                            triplets[i][j]);
                    }
                }
            }
            if (Arrays.equals(merged, target))
                return true;
        }
        return false;
    }
}

Complexity

Time Complexity: O(2^n × n)

There are 2^n - 1 non-empty subsets. For each subset, we iterate through all n triplets to check membership and compute the element-wise max. The 3-element max computation is O(1) per triplet. This is only feasible for n ≤ ~20.

Space Complexity: O(1)

Beyond the input, we only use the merged array of size 3 and a loop variable.

Why This Approach Is Not Efficient

The brute force checks 2^n - 1 subsets, which grows exponentially. For n = 20, that's about 1 million subsets — manageable. But for n = 30, it's over 1 billion, and for the actual constraint of n = 10^5, 2^100000 is an astronomically large number with over 30,000 digits.

The fundamental waste is that we treat every subset independently, even though many subsets share the same "problem" — they include a triplet that overshoots the target in some position.

Key insight: Notice what happened in our trace: triplet [1,8,4] appeared in every failed multi-element subset because its second value 8 exceeds the target's 7. We can identify such "poisonous" triplets upfront and exclude them entirely. A triplet is safe to use only if ALL three of its values are ≤ the corresponding target values. Among all safe triplets, we can freely merge them (the max can never exceed the target), so we just need to check whether the maximum value at each position across all safe triplets reaches exactly the target.

Optimal Approach - Greedy Filter

Intuition

The optimal solution relies on two insights about the merge operation:

Insight 1 — Merging can only increase values. Since we take the maximum at each position, values can only go up or stay the same. This means if a triplet has any value larger than the corresponding target value, that triplet is "poisonous" — including it in any merge would push that position past the target, and there's no way to bring it back down.

Insight 2 — Safe triplets can be freely combined. If every value in a triplet is ≤ the corresponding target value, that triplet is "safe." Merging any combination of safe triplets will never exceed the target in any position. So among all safe triplets, the best possible result is the element-wise maximum across all of them.

This gives us a beautifully simple algorithm:

  1. Filter: Skip any triplet where at least one value exceeds the target.
  2. Track maximums: For each safe triplet, update the running maximum at each position.
  3. Verify: After processing all triplets, check if the maximums equal the target.

The algorithm runs in a single pass — O(n) time with O(1) extra space. We don't need to track which triplets we used or simulate any merges. We just need to verify that the required values exist among the safe triplets.

Diagram showing three triplets being filtered: [2,5,3] and [1,7,5] marked safe with green checks, [1,8,4] marked unsafe with red X because 8 exceeds target 7. Safe triplets merge to exactly match target [2,7,5].
Diagram showing three triplets being filtered: [2,5,3] and [1,7,5] marked safe with green checks, [1,8,4] marked unsafe with red X because 8 exceeds target 7. Safe triplets merge to exactly match target [2,7,5].

Step-by-Step

Let's trace through triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5].

Initialize: Extract target values x=2, y=7, z=5. Set maximum trackers d=0, e=0, f=0.

Triplet [2,5,3]:

  • Safety check: Is 2 ≤ 2? ✓. Is 5 ≤ 7? ✓. Is 3 ≤ 5? ✓.
  • SAFE — all values within target bounds.
  • Update: d = max(0, 2) = 2, e = max(0, 5) = 5, f = max(0, 3) = 3.
  • Current maximums: [2, 5, 3].

Triplet [1,8,4]:

  • Safety check: Is 1 ≤ 2? ✓. Is 8 ≤ 7? ✗ (8 > 7).
  • UNSAFE — second value overshoots. Skip entirely.
  • Current maximums remain: [2, 5, 3].

Triplet [1,7,5]:

  • Safety check: Is 1 ≤ 2? ✓. Is 7 ≤ 7? ✓. Is 5 ≤ 5? ✓.
  • SAFE — all values within target bounds.
  • Update: d = max(2, 1) = 2, e = max(5, 7) = 7, f = max(3, 5) = 5.
  • Current maximums: [2, 7, 5].

Verify: Is [2, 7, 5] == [2, 7, 5]? YES! Return true.

The algorithm correctly identified that triplets 0 and 2 together supply all the values needed, while avoiding the poisonous triplet 1.

Initialize max trackers [d,e,f] = [0,0,0] — Initialize max trackers [d,e,f] = [0,0,0]. Target = [2,7,5].

Algorithm

  1. Extract target values x, y, z = target.
  2. Initialize maximum trackers d = 0, e = 0, f = 0.
  3. For each triplet [a, b, c]:
    • If a <= x AND b <= y AND c <= z (triplet is safe):
      • d = max(d, a)
      • e = max(e, b)
      • f = max(f, c)
    • Otherwise, skip the triplet.
  4. Return true if d == x AND e == y AND f == z, else false.

Code

class Solution {
public:
    bool mergeTriplets(vector<vector<int>>& triplets,
                       vector<int>& target) {
        int d = 0, e = 0, f = 0;
        for (auto& t : triplets) {
            if (t[0] <= target[0] &&
                t[1] <= target[1] &&
                t[2] <= target[2]) {
                d = max(d, t[0]);
                e = max(e, t[1]);
                f = max(f, t[2]);
            }
        }
        return d == target[0] &&
               e == target[1] &&
               f == target[2];
    }
};
class Solution:
    def mergeTriplets(self, triplets: List[List[int]],
                      target: List[int]) -> bool:
        x, y, z = target
        d = e = f = 0
        for a, b, c in triplets:
            if a <= x and b <= y and c <= z:
                d = max(d, a)
                e = max(e, b)
                f = max(f, c)
        return [d, e, f] == target
class Solution {
    public boolean mergeTriplets(int[][] triplets,
                                 int[] target) {
        int d = 0, e = 0, f = 0;
        for (int[] t : triplets) {
            if (t[0] <= target[0] &&
                t[1] <= target[1] &&
                t[2] <= target[2]) {
                d = Math.max(d, t[0]);
                e = Math.max(e, t[1]);
                f = Math.max(f, t[2]);
            }
        }
        return d == target[0] &&
               e == target[1] &&
               f == target[2];
    }
}

Complexity

Time Complexity: O(n)

We iterate through the triplets array exactly once. For each triplet, we perform a constant number of comparisons (3 for the safety check) and updates (3 max operations). Total: 3n comparisons + at most 3n max operations = O(n).

Space Complexity: O(1)

We use only three integer variables (d, e, f) regardless of input size. No additional data structures are needed.