Problem Statement

You are given a 2D array of integers triplets, where triplets[i] = [ai, bi, ci] represents the ith triplet. You are also given an array of integers target = [x, y, z] which is the triplet we want to obtain.

To obtain target, you may apply the following operation on triplets zero or more times:
Choose two different triplets triplets[i] and triplets[j] and update triplets[j] to become [max(ai, aj), max(bi, bj), max(ci, cj)].

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

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

Additional information

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

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 third triplets. Update the third triplet to be [max(2,1), max(5,7), max(3,5)] = [2,7,5].
  The third triplet is now equal to the target, so we return true.

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. Update the third triplet to be [max(2,1), max(5,2), max(3,5)] = [2,5,5].
• Choose the updated third triplet and the fourth triplet. Update the fourth triplet to be [max(2,5), max(5,2), max(5,3)] = [5,5,5].

Greedy Accumulation

Intuition

Because the only operation we can perform is taking the maximum of two elements, numbers can only stay the same or increase. They can never decrease.

This gives us a massive clue: if we look at a triplet and any of its three numbers is strictly greater than the corresponding number in our target, that triplet is completely useless. If we were to merge it with anything else, the resulting number would exceed our goal, and we could never undo it!

Therefore, we can simply ignore all "invalid" triplets. For all the remaining "valid" triplets, we can greedily merge them all together into a single running triplet. If this final running triplet matches our target, it means we successfully collected all the necessary pieces!

Algorithm

1. Initialize a merged array [0, 0, 0] to keep track of our running maximums.
2. Iterate through each triplet t in triplets.
3. Check if the triplet is valid. A triplet is valid only if t[0] <= target[0], t[1] <= target[1], and t[2] <= target[2].
4. If the triplet is valid, update our merged array by taking the element-wise maximum:

• merged[0] = max(merged[0], t[0])
• merged[1] = max(merged[1], t[1])
• merged[2] = max(merged[2], t[2])

5. After the loop finishes, check if merged == target. Return True if it does, False otherwise.

def merge_triplets(triplets: list[list[int]], target: list[int]) -> bool:
    merged = [0, 0, 0]
    
    for t in triplets:
        # Skip triplets that have any value exceeding the target
        if t[0] > target[0] or t[1] > target[1] or t[2] > target[2]:
            continue
            
        # Greedily accumulate the maximums of valid triplets
        merged[0] = max(merged[0], t[0])
        merged[1] = max(merged[1], t[1])
        merged[2] = max(merged[2], t[2])
        
    return merged == target

Time & Space Complexity

• Time complexity: O(N)

• Reason: We iterate through the triplets array exactly once. The comparisons and updates take constant O(1) time per triplet.

• Space complexity: O(1)

• Reason: We only allocate a single array of size 3 (merged) to track our state.

Early Exit Boolean Check - Optimal

Intuition

We can optimize the accumulation approach slightly. We don't actually need to mathematically merge the arrays and build the final triplet. We just need to confirm that among all the valid triplets, we can find the exact target value for the first position, the second position, and the third position.

We can maintain a set (or three boolean flags) to track which of the three target positions we have successfully matched. As we scan the valid triplets, if we find a match for a position, we record it. The moment we have matched all three positions, we can return True immediately, skipping the rest of the array!

Algorithm

1. Initialize an empty good_indices set. This will store 0, 1, or 2 when we find a match for that respective index.
2. Iterate through each t in triplets.
3. Check if the triplet is invalid (any element exceeds the target). If it is, continue to the next triplet.
4. Iterate i from 0 to 2 (checking the three elements of the triplet).

• If t[i] == target[i], add i to good_indices.

5. If len(good_indices) == 3, we have found all required pieces! Return True immediately.
6. If the loop finishes without the set reaching size 3, return False.

def merge_triplets(triplets: list[list[int]], target: list[int]) -> bool:
    good_indices = set()
    
    for t in triplets:
        # Ignore any triplet that would push us over the target limit
        if t[0] > target[0] or t[1] > target[1] or t[2] > target[2]:
            continue
            
        # Check which specific target values this valid triplet provides
        for i, val in enumerate(t):
            if val == target[i]:
                good_indices.add(i)
                
        # Early exit if we have matched all three positions
        if len(good_indices) == 3:
            return True
            
    return len(good_indices) == 3

Time & Space Complexity

• Time complexity: O(N)

• Reason: We iterate through the array at most once. The early exit ensures we stop the moment we have enough information, making it faster in practice than standard accumulation.

• Space complexity: O(1)

• Reason: The good_indices set will only ever hold a maximum of 3 integers (0, 1, and 2), which requires strictly constant memory.