Merge Triplets to Form Target: Keep Only Triplets That Never Overshoot

Problem

You have a list of triplets of integers and a target triplet. An operation picks two triplets and replaces one of them with their element-wise maximum. Decide whether, after any number of operations, the target can appear in the list.

This is widely known as LeetCode 1899, “Merge Triplets to Form Target Triplet”.

Assume up to 100,000 triplets with values up to 1,000.

Examples

triplets [[1, 4, 2], [3, 1, 5], [2, 2, 2]], target [3, 4, 5]
max of the first two = [3, 4, 5]                        -> True

triplets [[2, 6, 1], [1, 3, 3]], target [2, 3, 3]
[2, 6, 1] has 6 > 3 and is unusable; [1, 3, 3] alone lacks the 2   -> False

triplets [[5, 5, 5]], target [5, 5, 5]                   -> True

Approach 1: try every subset

A target is formed by merging some subset, so try them all.

def merge_triplets_brute(triplets, target):
    n = len(triplets)
    for mask in range(1, 1 << n):
        merged = [0, 0, 0]
        first = True
        for i in range(n):
            if mask >> i & 1:
                t = triplets[i]
                merged = list(t) if first else [max(a, b) for a, b in zip(merged, t)]
                first = False
        if merged == list(target):
            return True
    return False

O(2^n * n): only a test oracle.

Approach 2: optimal, greedy filter

Why it works

• A triplet with any value above the target’s value at that position can never be used: the maximum never shrinks.
• Every other triplet is safe: merging it cannot exceed the target anywhere.
• So the best you can do is merge all safe triplets. The result equals the target exactly when each position’s target value is achieved by at least one safe triplet.

Python solution

def merge_triplets(triplets, target):
    found = [False, False, False]
    for t in triplets:
        if t[0] > target[0] or t[1] > target[1] or t[2] > target[2]:
            continue
        for k in range(3):
            if t[k] == target[k]:
                found[k] = True
    return all(found)

Complexity

O(n) time, O(1) space.

Tests

for fn in (merge_triplets, merge_triplets_brute):
    assert fn([[1, 4, 2], [3, 1, 5], [2, 2, 2]], [3, 4, 5])
    assert not fn([[2, 6, 1], [1, 3, 3]], [2, 3, 3])
    assert fn([[5, 5, 5]], [5, 5, 5])                 # single triplet equal to target
    assert not fn([[1, 1, 1]], [2, 2, 2])             # never grows enough
    assert not fn([], [1, 1, 1])                      # no triplets
    assert fn([[3, 0, 0], [0, 3, 0], [0, 0, 3]], [3, 3, 3])

import random
random.seed(30)
for _ in range(200):
    ts = [[random.randint(0, 3) for _ in range(3)] for _ in range(random.randint(0, 6))]
    tg = [random.randint(0, 3) for _ in range(3)]
    assert merge_triplets(ts, tg) == merge_triplets_brute(ts, tg)

Edge cases and pitfalls

• Using a triplet that overshoots in any one position.
• Requiring one triplet to match fully. Different triplets may supply different positions.
• Empty list cannot form anything.

Where this shows up in data engineering

Element-wise maximum is how you merge watermarks or version vectors: combining per-source high-water marks only ever moves them forward. The filtering step is the same reasoning as discarding any partial result that has already gone past a cut-off, because it can never come back.