Solutions

# Brute force, or greedy by keeping track of which positions can contribute to the target triplet. 
# greedy

# Brute force - O(n^2) time, O(1) space
def mergeTriplets(triplets: list[list[int]], target: list[int]) -> bool:
    for a in triplets:
        if a[0] > target[0] or a[1] > target[1] or a[2] > target[2]:
            continue
        if a == target:
            return True

        cumul = a
        for b in triplets:
            if a == b:
                continue

            res = [max(a[0], b[0]), max(a[1], b[1]), max(a[2], b[2])]
            cumul = [max(cumul[0],b[0]), max(cumul[1], b[1]), max(cumul[2], b[2])]
            if res == target or cumul == target:
                return True

    return False


# Greedy - O(n) time, O(1) space
def mergeTriplets(triplets: list[list[int]], target: list[int]) -> bool:
    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


# Greedy (optimal) - O(n) time, O(1) space
def mergeTriplets(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