Merge Triplets to Form Target

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)].

• E.g. 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 target as an element of triplets, or false otherwise.

Example 1:

Input: triplets = [[1,2,3],[7,1,1]], target = [7,2,3]

Output: True

Explanation: Choose the first and second triplets, update the second triplet to be [max(1, 7), max(2, 1), max(3, 1)] = [7, 2, 3].

Example 2:

Input: triplets = [[2,5,6],[1,4,4],[5,7,5]], target = [5,4,6]

Output: False

Constraints:

• 1 <= triplets.length <= 1000
• 1 <= ai, bi, ci, x, y, z <= 100

Recommended Time and Space Complexity

You should aim for a solution with O(n) time and O(1) space, where n is the number of triplets.

Hint 1

Consider which triplets could possibly contribute to forming the target. Any triplet with a value greater than the corresponding target value cannot be used.

Hint 2

Iterate through the triplets and check if each value is less than or equal to the corresponding target value. If not, that triplet can’t be used.

Hint 3

Keep track of whether you’ve found a triplet that matches each of the target values in the correct position.

Solution

Greedy

def merge_triplets(triplets: list[list[int]], target: list[int]) -> bool:
    """
    Determines if it's possible to merge triplets to form the target.

    Args:
        triplets: A list of triplets (lists of 3 integers).
        target: The target triplet (list of 3 integers).

    Returns:
        True if the target can be formed, False otherwise.
    """
    good = set()

    for t in triplets:
        if t[0] > target[0] or t[1] > target[1] or t[2] > target[2]:
            continue
        for i, v in enumerate(t):
            if v == target[i]:
                good.add(i)
    return len(good) == 3

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