Merge Triplets to Form Target Triplet

Difficulty: Medium Source: NeetCode

Problem

A triplet is an array of three integers. You are given a 2D array triplets and a target triplet target. Merging two triplets means: [max(a,d), max(b,e), max(c,f)]. You can merge any two triplets any number of times. Return true if you can form target from the given triplets.

Example 1: Input: triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5] Output: true Explanation: Merge [2,5,3] and [1,7,5] → [2,7,5].

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

Constraints:

• 1 <= triplets.length <= 10^5
• triplets[i].length == target.length == 3
• 1 <= triplets[i][j], target[j] <= 1000

Prerequisites

Before attempting this problem, you should be comfortable with:

• Greedy filtering — eliminating candidates that can’t contribute
• Component-wise max — understanding what merging does

1. Brute Force

Intuition

Try all subsets of triplets, merge them, and check if any subset produces the target. A subset is merged by taking the component-wise max. Checking all 2^n subsets is too slow for large inputs.

Algorithm

1. For every subset of triplets:
   • Merge by taking max at each position.
   • If the result equals target, return True.
2. Return False.

Solution

def mergeTriplets(triplets, target):
    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


print(mergeTriplets([[2, 5, 3], [1, 8, 4], [1, 7, 5]], [2, 7, 5]))  # True
print(mergeTriplets([[3, 4, 5], [4, 5, 6]], [3, 2, 5]))              # False
print(mergeTriplets([[2, 5, 3], [2, 3, 4], [1, 2, 5]], [2, 5, 5]))  # True

Complexity

• Time: O(2^n * n) — exponential, only feasible for tiny inputs
• Space: O(1)

2. Greedy — Filter Then Check Component Coverage

Intuition

Key observation: if any element of a triplet exceeds the corresponding target element, using that triplet in a merge would permanently push that position above the target (since merge is max). So we can safely ignore such “bad” triplets.

After filtering, take the component-wise max of all remaining triplets. If the result equals target, we can form it. Otherwise, we can’t.

Why does this work? Any triplet that doesn’t exceed the target in any position can only help, never hurt. And if the remaining triplets’ max per position equals the target, we’ve shown each target value is achievable.

Algorithm

1. Filter out triplets where any element exceeds the corresponding target element.
2. Take the component-wise max across all remaining triplets.
3. Return True if the result equals target.

Solution

def mergeTriplets(triplets, target):
    result = [0, 0, 0]

    for t in triplets:
        # Skip triplets that would overshoot any target component
        if t[0] > target[0] or t[1] > target[1] or t[2] > target[2]:
            continue
        # Merge into result
        for j in range(3):
            result[j] = max(result[j], t[j])

    return result == target


print(mergeTriplets([[2, 5, 3], [1, 8, 4], [1, 7, 5]], [2, 7, 5]))  # True
print(mergeTriplets([[3, 4, 5], [4, 5, 6]], [3, 2, 5]))              # False
print(mergeTriplets([[2, 5, 3], [2, 3, 4], [1, 2, 5]], [2, 5, 5]))  # True
print(mergeTriplets([[1, 1, 1]], [1, 1, 1]))                          # True
print(mergeTriplets([[1, 1, 1], [1, 2, 1]], [1, 2, 1]))              # True


# Using any() for cleaner filtering
def mergeTriplets_v2(triplets, target):
    result = [0, 0, 0]
    for t in triplets:
        if any(t[j] > target[j] for j in range(3)):
            continue
        for j in range(3):
            result[j] = max(result[j], t[j])
    return result == target


print(mergeTriplets_v2([[2, 5, 3], [1, 8, 4], [1, 7, 5]], [2, 7, 5]))  # True

Complexity

• Time: O(n) — single pass through triplets
• Space: O(1)

Common Pitfalls

Not filtering triplets that exceed the target. If you merge a triplet with value 8 in position 1 when target[1] = 7, the merged result will have 8 at position 1 — permanently exceeding the target. Always skip such triplets.

Returning True when result covers target but has higher values. The result must equal the target exactly, not just dominate it. After merging filtered triplets, check result == target, not result >= target.

Thinking order of merging matters. Merge is commutative and associative (it’s just component-wise max). Order doesn’t matter — we can merge in any order and get the same final result.