Merge Triplets to Form Target Triplet

Problem Description

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 target triplet.

To form the target triplet, you can perform the following operation on triplets any number of times (possibly zero):

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

For example, if triplets[i] = [2, 5, 3] and triplets[j] = [1, 7, 5], triplets[j] will be updated to [max(2, 1), max(5, 7), max(3, 5)] = [2, 7, 5].

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
Explanation: Perform the following operations:
- Choose the first and last triplets [[2,5,3],[1,8,4],[1,7,5]]. Update the last triplet to be [max(2,1), max(5,7), max(3,5)] = [2,7,5]. triplets = [[2,5,3],[1,8,4],[2,7,5]]
The target triplet [2,7,5] is now an element of triplets.

Example 2:

Input: triplets = [[3,4,5],[4,5,6]], target = [3,2,5]
Output: false
Explanation: It is impossible to have [3,2,5] as an element because there is no 2 in any of the triplets.

Example 3:

Input: triplets = [[2,5,3],[2,3,4],[1,2,5],[5,2,3]], target = [5,5,5]
Output: true
Explanation: Perform the following operations:
- Choose the first and third triplets [[2,5,3],[2,3,4],[1,2,5],[5,2,3]]. Update the third triplet to be [max(2,1), max(5,2), max(3,5)] = [2,5,5]. triplets = [[2,5,3],[2,3,4],[2,5,5],[5,2,3]].
- Choose the third and fourth triplets [[2,5,3],[2,3,4],[2,5,5],[5,2,3]]. Update the fourth triplet to be [max(2,5), max(5,2), max(5,3)] = [5,5,5]. triplets = [[2,5,3],[2,3,4],[2,5,5],[5,5,5]].
The target triplet [5,5,5] is now an element of triplets.

Constraints

• 1 <= triplets.length <= 10^5
• triplets[i].length == target.length == 3
• 1 <= ai, bi, ci, x, y, z <= 1000

Solution Approach

This problem can be solved using a greedy approach:

Key Insight

Since we can only take the maximum of values when merging triplets, we can never decrease any value. If a triplet has any value greater than the corresponding target value, we can never use it (as it would make the result exceed the target).

Algorithm

1. Skip invalid triplets: If any element in a triplet is greater than the corresponding target element, skip it entirely.
2. Track achievable positions: For each valid triplet, check which positions match the target exactly.
3. Check if all positions are achievable: We can form the target if and only if we can achieve all three positions from the valid triplets.

Greedy Strategy

We don't need to actually perform the merging operations. We just need to check if:

• There exists at least one triplet where triplet[0] == target[0] (and no value exceeds target)
• There exists at least one triplet where triplet[1] == target[1] (and no value exceeds target)
• There exists at least one triplet where triplet[2] == target[2] (and no value exceeds target)

These can be from the same or different triplets - it doesn't matter!

Time & Space Complexity

• Time Complexity: O(n) where n is the number of triplets
• Space Complexity: O(1) - only using a boolean array of size 3

Java Solution

class Solution {
    public boolean mergeTriplets(int[][] triplets, int[] target) {
        boolean[] canAchieve = new boolean[3];

        for (int[] triplet : triplets) {
            // Skip if any value exceeds target
            if (triplet[0] > target[0] ||
                triplet[1] > target[1] ||
                triplet[2] > target[2]) {
                continue;
            }

            // Mark positions that match target
            if (triplet[0] == target[0]) canAchieve[0] = true;
            if (triplet[1] == target[1]) canAchieve[1] = true;
            if (triplet[2] == target[2]) canAchieve[2] = true;
        }

        return canAchieve[0] && canAchieve[1] && canAchieve[2];
    }
}

Python Solution

def mergeTriplets(triplets: List[List[int]], target: List[int]) -> bool:
    can_achieve = [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 positions that match target
        if triplet[0] == target[0]: can_achieve[0] = True
        if triplet[1] == target[1]: can_achieve[1] = True
        if triplet[2] == target[2]: can_achieve[2] = True

    return all(can_achieve)