LeetEye LeetEye
Medium Greedy ~5 min

Merge Triplets to Form Target Triplet

greedy merge-triplets-to-form-target-triplet

Problem

A triplet is an array of three integers. You are given a 2D integer array triplets, where triplets[i] = [ai, bi, ci] describes the ith 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 on triplets any number of times:

Choose two indices i and j (i != j) and update triplets[j] to become [max(ai, aj), max(bi, bj), max(ci, cj)].

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

Examples

Example 1
Input: triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5]
Output: true
Merge triplets[0] and triplets[2]: [max(2,1), max(5,7), max(3,5)] = [2,7,5]
Example 2
Input: triplets = [[3,4,5],[4,5,6]], target = [3,2,5]
Output: false
Key Insight

A triplet is usable only if ALL its values are ≤ corresponding target values.

Filter triplets where ALL values ≤ target (usable). Among usable ones, check if we can find each target value exactly. Max never decreases values.

How to Approach This Problem

Pattern Recognition: When you see keywords like merge triplets to form target triplet greedy, think Greedy.

Step-by-Step Reasoning

1 After taking max of two triplets:
Answer: Values can only increase or stay same
max(a, b) >= a and max(a, b) >= b. Values never decrease.
2 A triplet [a, b, c] is unusable if:
Answer: Any value exceeds corresponding target
If a > target[0], using this triplet will make result[0] > target[0], which we can never reduce.
3 We need to find valid triplets that together:
Answer: Cover all target values exactly
We need some triplet with value = target[0], some with = target[1], some with = target[2].
4 For each valid triplet, we track:
Answer: Which target positions it matches exactly
If triplet[i] == target[i], this triplet can "contribute" that target value.
5 We succeed if:
Answer: Valid triplets together cover all 3 positions
Collectively, valid triplets must have each target value achievable.

Solution

def mergeTriplets(triplets: List[List[int]], target: List[int]) -> bool:
    found = [False, False, False]
    
    for triplet in triplets:
        # Skip if any value exceeds target
        if triplet[0] > target[0] or triplet[1] > target[1] or triplet[2] > target[2]:
            continue
        
        # Mark which target values this triplet can contribute
        for i in range(3):
            if triplet[i] == target[i]:
                found[i] = True
    
    return all(found)

Complexity Analysis

Time O(n)
Space O(1)

Master This Pattern

Build intuition with interactive MCQs. Practice Greedy problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye