Merge Triplets to Form Target Triplet

How it works

We are given several triplets and a target triplet. When we merge triplets, we take the maximum value at each index, so values can only increase, never decrease.

This leads to an important rule:

• Any triplet that has a value greater than the target at any index cannot be used to form the target.

Instead of collecting indices in a set, we can think more directly:

• To reach target[0], we need at least one triplet where:
  • the first value equals target[0]
  • the other two values do not exceed the target
• Similarly for target[1] and target[2]

If we can independently satisfy all three positions using valid triplets, then merging those triplets will exactly form the target.

Steps

1. Initialize three boolean flags:
   • x → can we match target[0]?
   • y → can we match target[1]?
   • z → can we match target[2]?
2. Iterate through each triplet t:
3. Update the flags:
   • Set x = true if:
     • t[0] == target[0]
     • t[1] <= target[1]
     • t[2] <= target[2]
   • Set y = true if:
     • t[1] == target[1]
     • t[0] <= target[0]
     • t[2] <= target[2]
   • Set z = true if:
     • t[2] == target[2]
     • t[0] <= target[0]
     • t[1] <= target[1]
4. If at any point all three flags x, y, and z become true:
   • return true immediately
5. If the loop finishes and not all flags are true:
   • return false

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Things to watch for

Including Triplets With Values Exceeding the Target

A triplet where any element exceeds the corresponding target value can never be used because merging only takes the maximum at each position, so values can only increase. Failing to filter out these invalid triplets leads to incorrect results.

Checking Only for Exact Target Matches Without Filtering

Some solutions check if a triplet matches the target at a position but forget to verify that the other positions do not exceed the target. A triplet like [5, 2, 3] matching target[0] = 5 is useless if target[1] = 1 because the 2 exceeds it.

Thinking You Need to Find a Single Triplet Equaling the Target

The problem allows merging multiple triplets. You do not need one triplet that exactly equals the target. You need to find triplets that collectively can contribute each target value independently while never exceeding any target position.

from typing import List

class Solution:
    def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool:
        x = y = z = False
        for t in triplets:
            x |= (t[0] == target[0] and t[1] <= target[1] and t[2] <= target[2])
            y |= (t[0] <= target[0] and t[1] == target[1] and t[2] <= target[2])
            z |= (t[0] <= target[0] and t[1] <= target[1] and t[2] == target[2])
            if x and y and z:
                return True
        return False

class Solution {
public:
    bool mergeTriplets(vector<vector<int>>& triplets, vector<int>& target) {
        bool x = false, y = false, z = false;
        for (const auto& t : triplets) {
            x |= (t[0] == target[0] && t[1] <= target[1] && t[2] <= target[2]);
            y |= (t[0] <= target[0] && t[1] == target[1] && t[2] <= target[2]);
            z |= (t[0] <= target[0] && t[1] <= target[1] && t[2] == target[2]);
            if (x && y && z) return true;
        }
        return false;
    }
};