Merge Triplets to Form Target Triplet: Greedy Filtering

You are given a list of triplets [a, b, c] and a target triplet [x, y, z]. You can merge any two triplets by taking the element-wise maximum, producing [max(a1, a2), max(b1, b2), max(c1, c2)]. The question is whether you can form the exact target through a sequence of these merge operations.

This is LeetCode 1899: Merge Triplets to Form Target Triplet, a medium problem that looks like it might need search or simulation but actually collapses into a simple greedy filter. Once you see the key observation, the solution is just a few lines.

The problem

LeetCode 1899: Merge Triplets to Form Target Triplet. You have a 2D array of triplets and a target triplet. You can pick any two triplets and replace one of them with their element-wise max. After any number of operations, determine if you can produce a triplet that equals the target exactly.

The greedy insight

The merge operation takes the maximum of each position. That means values can only stay the same or go up, never down. If any triplet has a value that exceeds the target in any position, merging it with anything else would push that position above the target permanently. So that triplet is useless.

This gives you the first filter: discard every triplet where any element exceeds the corresponding target element. These triplets can never participate in building the target.

Among the remaining "usable" triplets, you just need to check coverage. For each position in the target (0, 1, 2), at least one usable triplet must have exactly the target value at that position. If all three positions are covered, you can merge those triplets together to form the target. If any position is missing, it is impossible.

Why does coverage guarantee success? Because all usable triplets have values that are at most the target in every position. Taking the max of any subset of them can only produce values between the minimum and maximum values present across that subset. Since no value exceeds the target, and at least one value equals the target at each position, the result of merging all usable triplets will hit the target at every position.

Visual walkthrough

The code

def merge_triplets(triplets, target):
    found = [False, False, False]

    for triplet in triplets:
        if all(triplet[i] <= target[i] for i in range(3)):
            for i in range(3):
                if triplet[i] == target[i]:
                    found[i] = True

    return all(found)

The outer loop scans every triplet once. For each triplet, the all(triplet[i] <= target[i] ...) check determines if the triplet is usable. If any element exceeds the target, we skip it entirely. For usable triplets, we check each of the three positions. If the value matches the target at position i, we mark that position as covered.

After scanning all triplets, we check whether all three positions are covered. If every element of found is True, we can form the target and return True. Otherwise, at least one target value is unreachable and we return False.

The logic is a two-phase filter: first reject anything that would overshoot, then verify that what remains can collectively hit every target value.

Complexity analysis

Since each triplet has exactly three elements, the inner loops are constant-time. The algorithm processes each triplet once, so the total time is linear in the number of triplets. No extra data structures are needed beyond the three-element boolean tracker.

The building blocks

1. Greedy filtering. The pattern of eliminating candidates that violate a constraint before checking feasibility. Here, any triplet with an element exceeding the target is discarded. This same "prune first, verify second" structure appears in problems like Gas Station (eliminating starting points that cause a deficit) and Jump Game (skipping positions beyond your reach).

2. Coverage checking. After filtering, you verify that the remaining elements collectively satisfy every requirement. This is similar to checking if a set of intervals covers a full range, or whether a collection of characters covers an entire alphabet. The key is that you only need existence (at least one match per position), not a specific combination.

3. Monotonic operation reasoning. The max operation can only increase values. Recognizing that a merge operation is monotone lets you reason about what is reachable without simulating every possible merge sequence. Whenever an operation is monotone, you can often reduce a search problem to a simple feasibility check.

Edge cases

• Single triplet that equals the target: no merges needed. The filter keeps it, coverage is complete, return True.
• No triplet has the target's first element: even if other positions are covered, found[0] stays False. Return False.
• All triplets exceed the target in some position: every triplet gets filtered out, nothing covers any position. Return False.
• Multiple triplets needed for coverage: for example, one covers position 0 and another covers positions 1 and 2. The algorithm handles this naturally since found accumulates across all usable triplets.
• Duplicate triplets: duplicates do not change the result. The algorithm processes them but the boolean flags are already True after the first match.

From understanding to recall

You have read the greedy solution and it makes sense. Filter out anything that overshoots, then check coverage. Two clean phases, no simulation, no recursion. But the real test is writing it from memory in an interview.

The details are small but matter: checking all(triplet[i] <= target[i]) as the filter condition, not just one position. Using == for the coverage check, not >=. These are the kinds of things that trip you up under pressure if you have only read the solution once.

Spaced repetition turns understanding into recall. You practice writing the filter-and-check loop from scratch at increasing intervals. After a few rounds, the pattern is automatic. You see "element-wise max, can you form a target?" and the code flows out without hesitation. The greedy filter pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling with spaced repetition is far more effective than grinding random problems.

Related posts

• Jump Game - Another greedy feasibility problem
• Gas Station - Greedy with coverage reasoning
• Maximum Subarray - Classic greedy problem